1 : // Copyright 2012 Google Inc. All Rights Reserved.
2 : //
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 : // Provides an assembler that assembles to basic block instruction lists.
16 :
17 : #ifndef SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_ASSEMBLER_H_
18 : #define SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_ASSEMBLER_H_
19 :
20 : #include "syzygy/block_graph/basic_block.h"
21 : #include "syzygy/core/assembler.h"
22 :
23 : namespace block_graph {
24 :
25 : using core::ValueSize;
26 :
27 : // Forward declarations.
28 : class BasicBlockAssembler;
29 : class Operand;
30 :
31 : // Declares a BasicBlockReference-like class that has no type or size
32 : // information. The size information is stored in the Operand or Value housing
33 : // the untyped reference, and the type is inferred from the instruction being
34 : // assembled.
35 : class UntypedReference {
36 : public:
37 : typedef BlockGraph::Block Block;
38 : typedef BlockGraph::Offset Offset;
39 :
40 : // Default constructor.
41 E : UntypedReference()
42 : : basic_block_(NULL), block_(NULL), offset_(0), base_(0) {
43 E : }
44 :
45 : // Copy constructor.
46 : // @param other The reference to be copied.
47 : UntypedReference(const UntypedReference& other)
48 : : basic_block_(other.basic_block_), block_(other.block_),
49 E : offset_(other.offset_), base_(other.base_) {
50 E : }
51 :
52 : // Constructor from a basic block reference.
53 : // @param bb_ref The basic block reference to be copied.
54 : explicit UntypedReference(const BasicBlockReference& bb_ref)
55 : : basic_block_(bb_ref.basic_block()), block_(bb_ref.block()),
56 E : offset_(bb_ref.offset()), base_(bb_ref.base()) {
57 E : DCHECK(block_ != NULL || basic_block_ != NULL);
58 E : }
59 :
60 : // Constructs a reference to a basic block.
61 : // @param basic_block The basic block to be referred to.
62 E : explicit UntypedReference(BasicBlock* basic_block)
63 : : basic_block_(basic_block), block_(NULL), offset_(0), base_(0) {
64 E : DCHECK(basic_block != NULL);
65 E : }
66 :
67 : // Constructs a reference to a block.
68 : // @param block The block to be referred to.
69 : // @param offset The offset from the start of the block actually being
70 : // pointed to.
71 : // @param base The offset from the start of the block semantically being
72 : // referred to.
73 E : UntypedReference(Block* block, Offset offset, Offset base)
74 : : basic_block_(NULL), block_(block), offset_(offset), base_(base) {
75 E : DCHECK(block != NULL);
76 E : }
77 :
78 : // @name Accessors.
79 : // @{
80 E : BasicBlock* basic_block() const { return basic_block_; }
81 E : Block* block() const { return block_; }
82 E : Offset offset() const { return offset_; }
83 E : Offset base() const { return base_; }
84 : // @}
85 :
86 : // @returns true if this reference is valid.
87 E : bool IsValid() const { return block_ != NULL || basic_block_ != NULL; }
88 :
89 : // Returns the type of the object being referred to.
90 E : BasicBlockReference::ReferredType referred_type() const {
91 E : if (block_ != NULL)
92 E : return BasicBlockReference::REFERRED_TYPE_BLOCK;
93 E : if (basic_block_ != NULL)
94 E : return BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK;
95 E : return BasicBlockReference::REFERRED_TYPE_UNKNOWN;
96 E : }
97 :
98 : // Comparison operator.
99 : // @returns true if this reference is the same as the @p other.
100 E : bool operator==(const UntypedReference& other) const {
101 : return basic_block_ == other.basic_block_ &&
102 : block_ == other.block_ &&
103 : offset_ == other.offset_ &&
104 E : base_ == other.base_;
105 E : }
106 :
107 : private:
108 : BasicBlock* basic_block_;
109 : Block* block_;
110 : Offset offset_;
111 : Offset base_;
112 : };
113 :
114 : class Value {
115 : public:
116 : typedef BlockGraph::Block Block;
117 : typedef BlockGraph::Offset Offset;
118 : typedef core::ValueImpl ValueImpl;
119 : typedef core::ValueSize ValueSize;
120 :
121 : // Default construction.
122 : Value();
123 :
124 : // Constructs an 8- or 32-bit value, depending on the minimum number of bits
125 : // required to represent the Value. If the value can be encoded using 8-bits
126 : // to have the same representation under sign extension, then an 8-bit Value
127 : // will be created; otherwise, a 32-bit absolute Value will be created.
128 : // @param value The value to be stored.
129 : explicit Value(uint32 value);
130 :
131 : // Constructs an absolute value having a specific bit width.
132 : // @param value The value to be stored.
133 : // @param size The size of the value.
134 : Value(uint32 value, ValueSize size);
135 :
136 : // Constructs a 32-bit direct reference to the basic block @p bb.
137 : // @param bb The basic block to be referred to.
138 : // @note This is fine even for jmps (which may be encoded using 8-bit
139 : // references) as the BB layout algorithm will use the shortest jmp
140 : // possible.
141 : explicit Value(BasicBlock* bb);
142 :
143 : // Constructs a 32-bit direct reference to @p block at the given @p offset.
144 : // @param block The block to be referred to.
145 : // @param offset The offset to be referred to, both semantically and
146 : // literally. The base and offset of the reference will be set to this.
147 : // @note This is fine even for jmps (which may be encoded using 8-bit
148 : // references) as the BB layout algorithm will use the shortest jmp
149 : // possible.
150 : Value(Block* block, Offset offset);
151 :
152 : // Constructs a 32-bit reference to @p block at the given @p offset and
153 : // @p base.
154 : // @param block The block to be referred to.
155 : // @param offset The offset to be literally referred to.
156 : // @param base The offset to be semantically referred to. This must be
157 : // within the data of @p block.
158 : Value(Block* block, Offset offset, Offset base);
159 :
160 : // Full constructor.
161 : // @param value The value to be stored.
162 : // @param size The size of the value.
163 : // @param ref The untyped reference backing this value. The reference must
164 : // be valid.
165 : Value(uint32 value, ValueSize size, const UntypedReference& ref);
166 :
167 : // Copy constructor.
168 : // @param other The value to be copied.
169 : Value(const Value& other);
170 :
171 : // Destructor.
172 : ~Value();
173 :
174 : // Assignment operator.
175 : const Value& operator=(const Value& other);
176 :
177 : // @name Accessors.
178 : // @{
179 E : uint32 value() const { return value_.value(); }
180 E : ValueSize size() const { return value_.size(); }
181 E : const UntypedReference& reference() const { return reference_; }
182 : // @}
183 :
184 : // Comparison operator.
185 : bool operator==(const Value& rhs) const;
186 :
187 : private:
188 : // Private constructor for Operand.
189 : Value(const UntypedReference& ref, const core::ValueImpl& value);
190 :
191 : friend class BasicBlockAssembler;
192 : friend class Operand;
193 :
194 : UntypedReference reference_;
195 : ValueImpl value_;
196 : };
197 :
198 : // Displacements and immediates behave near-identically, but are semantically
199 : // slightly different.
200 : typedef Value Immediate;
201 : typedef Value Displacement;
202 :
203 : // An operand implies indirection to memory through one of the myriad
204 : // modes supported by IA32.
205 : class Operand {
206 : public:
207 : // A register-indirect mode.
208 : explicit Operand(core::Register base);
209 :
210 : // A register-indirect with displacement mode.
211 : Operand(core::Register base, const Displacement& displ);
212 :
213 : // A displacement-only mode.
214 : explicit Operand(const Displacement& displ);
215 :
216 : // The full [base + index * scale + displ32] mode.
217 : // @note esp cannot be used as an index register.
218 : Operand(core::Register base,
219 : core::Register index,
220 : core::ScaleFactor scale,
221 : const Displacement& displ);
222 :
223 : // The full [base + index * scale] mode.
224 : // @note esp cannot be used as an index register.
225 : Operand(core::Register base,
226 : core::Register index,
227 : core::ScaleFactor scale);
228 :
229 : // The [index * scale + displ32] mode.
230 : // @note esp cannot be used as an index register.
231 : Operand(core::Register index,
232 : core::ScaleFactor scale,
233 : const Displacement& displ);
234 :
235 : // Copy constructor.
236 : Operand(const Operand& o);
237 :
238 : // Destructor.
239 : ~Operand();
240 :
241 : // Assignment operator.
242 : const Operand& operator=(const Operand& other);
243 :
244 : // @name Accessors.
245 : // @{
246 E : core::RegisterCode base() const { return operand_.base(); }
247 E : core::RegisterCode index() const { return operand_.index(); }
248 E : core::ScaleFactor scale() const { return operand_.scale(); }
249 E : Displacement displacement() const {
250 E : return Displacement(reference_, operand_.displacement());
251 E : }
252 : // @}
253 :
254 : private:
255 : friend class BasicBlockAssembler;
256 :
257 : UntypedReference reference_;
258 : core::OperandImpl operand_;
259 : };
260 :
261 : class BasicBlockAssembler {
262 : public:
263 : typedef BlockGraph::Block::SourceRange SourceRange;
264 : typedef BasicBlock::Instructions Instructions;
265 : typedef core::Register Register;
266 : typedef core::ConditionCode ConditionCode;
267 :
268 : // Constructs a basic block assembler that inserts new instructions
269 : // into @p *list at @p where.
270 : BasicBlockAssembler(const Instructions::iterator& where,
271 : Instructions *list);
272 :
273 : // Constructs a basic block assembler that inserts new instructions into
274 : // @p *list at @p where, assuming a starting address of @p location.
275 : BasicBlockAssembler(uint32 location,
276 : const Instructions::iterator& where,
277 : Instructions *list);
278 :
279 : // @returns The source range injected into created instructions.
280 E : SourceRange source_range() const { return serializer_.source_range(); }
281 :
282 : // Set the SourceRange injected repeatedly into each instruction created via
283 : // the assembler. This should be used with care because it causes the OMAP
284 : // information to no longer be 1:1 mapping, and may confuse some debuggers.
285 : // @param source_range The source range set to each created instructions.
286 E : void set_source_range(const SourceRange& source_range) {
287 E : serializer_.set_source_range(source_range);
288 E : }
289 :
290 : // @name Call instructions.
291 : // @{
292 : void call(const Immediate& dst);
293 : void call(const Operand& dst);
294 : // @}
295 :
296 : // @name Jmp instructions.
297 : // @{
298 : void jmp(const Immediate& dst);
299 : void jmp(const Operand& dst);
300 : // @}
301 :
302 : // @name Conditional branch instruction.
303 : // @{
304 : void j(ConditionCode code, const Immediate& dst);
305 : // @}
306 :
307 : // @name Manipulation of flags.
308 : // @{
309 : void pushfd();
310 : void popfd();
311 : void lahf();
312 : void sahf();
313 : void set(ConditionCode code, Register dst);
314 : // @}
315 :
316 : // @name Arithmetic operations.
317 : // @{
318 : void test_b(Register dst, Register src);
319 : void test_b(Register dst, const Immediate& src);
320 :
321 : void test(Register dst, Register src);
322 : void test(Register dst, const Operand& src);
323 : void test(const Operand& dst, Register src);
324 : void test(Register dst, const Immediate& src);
325 : void test(const Operand& dst, const Immediate& src);
326 :
327 : void cmp_b(Register dst, Register src);
328 : void cmp_b(Register dst, const Immediate& src);
329 :
330 : void cmp(Register dst, Register src);
331 : void cmp(Register dst, const Operand& src);
332 : void cmp(const Operand& dst, Register src);
333 : void cmp(Register dst, const Immediate& src);
334 : void cmp(const Operand& dst, const Immediate& src);
335 :
336 : void add_b(Register dst, Register src);
337 : void add_b(Register dst, const Immediate& src);
338 :
339 : void add(Register dst, Register src);
340 : void add(Register dst, const Operand& src);
341 : void add(const Operand& dst, Register src);
342 : void add(Register dst, const Immediate& src);
343 : void add(const Operand& dst, const Immediate& src);
344 :
345 : void sub_b(Register dst, Register src);
346 : void sub_b(Register dst, const Immediate& src);
347 :
348 : void sub(Register dst, Register src);
349 : void sub(Register dst, const Operand& src);
350 : void sub(const Operand& dst, Register src);
351 : void sub(Register dst, const Immediate& src);
352 : void sub(const Operand& dst, const Immediate& src);
353 : // @}
354 :
355 : // @name Shifting operations.
356 : // @{
357 : void shl(Register dst, const Immediate& src);
358 : void shr(Register dst, const Immediate& src);
359 : // @}
360 :
361 : // @name Byte mov varieties.
362 : // @{
363 : void mov_b(const Operand& dst, const Immediate& src);
364 : void movzx_b(Register dst, const Operand& src);
365 : // @}
366 :
367 : // @name Double-word mov varieties.
368 : // @{
369 : void mov(Register dst, Register src);
370 : void mov(Register dst, const Operand& src);
371 : void mov(const Operand& dst, Register src);
372 : void mov(Register dst, const Immediate& src);
373 : void mov(const Operand& dst, const Immediate& src);
374 : void mov_fs(Register dst, const Operand& src);
375 : void mov_fs(const Operand& dst, Register src);
376 : // @}
377 :
378 : // @name Load effective address.
379 : void lea(Register dst, const Operand& src);
380 :
381 : // @name Stack manipulation.
382 : // @{
383 : void push(Register src);
384 : void push(const Immediate& src);
385 : void push(const Operand& src);
386 :
387 : void pop(Register dst);
388 : void pop(const Operand& dst);
389 : // @}
390 :
391 : // @name Ret instructions.
392 : // @{
393 : void ret();
394 : void ret(uint16 n);
395 : // @}
396 :
397 : private:
398 : typedef BlockGraph::ReferenceType ReferenceType;
399 :
400 : class BasicBlockSerializer
401 : : public core::AssemblerImpl::InstructionSerializer {
402 : public:
403 : BasicBlockSerializer(const Instructions::iterator& where,
404 : Instructions* list);
405 :
406 : virtual void AppendInstruction(uint32 location,
407 : const uint8* bytes,
408 : size_t num_bytes,
409 : const size_t *ref_locations,
410 : const void* const* refs,
411 : size_t num_refs) OVERRIDE;
412 :
413 E : SourceRange source_range() const { return source_range_; }
414 E : void set_source_range(const SourceRange& source_range) {
415 E : source_range_ = source_range;
416 E : }
417 :
418 : // Pushes back a reference type to be associated with a untyped reference.
419 : // @param type The type of the reference.
420 : // @param size The size of the reference, as a ValueSize.
421 : void PushReferenceInfo(ReferenceType type, core::ValueSize size);
422 :
423 : private:
424 : struct ReferenceInfo {
425 : BlockGraph::ReferenceType type;
426 : size_t size; // In bytes.
427 : };
428 :
429 : Instructions::iterator where_;
430 : Instructions* list_;
431 :
432 : // Source range set to instructions appended by this serializer.
433 : SourceRange source_range_;
434 :
435 : // The reference types and sizes associated with references in the
436 : // instructions parameters. These are provided to the serializer out of
437 : // band (not via Operand/Immediate/Value) by the implementations of the
438 : // various instructions. They allow the corresponding UntypedReferences to
439 : // be completed.
440 : ReferenceInfo ref_infos_[2];
441 : size_t num_ref_infos_;
442 : };
443 :
444 : // @name Utility functions for pushing/validating reference info.
445 : // @{
446 : void PushMandatoryReferenceInfo(ReferenceType type, const Immediate& imm);
447 : void PushOptionalReferenceInfo(ReferenceType type, const Immediate& imm);
448 : void PushOptionalReferenceInfo(ReferenceType type, const Operand& op);
449 : void CheckReferenceSize(core::ValueSize size, const Immediate& imm) const;
450 : void CheckReferenceSize(core::ValueSize size, const Operand& op) const;
451 : // @}
452 :
453 : BasicBlockSerializer serializer_;
454 : core::AssemblerImpl asm_;
455 : };
456 :
457 : } // namespace block_graph
458 :
459 : #endif // SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_ASSEMBLER_H_
|