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 the Basic-Block Graph representation and APIs.
16 : //
17 : // See http://en.wikipedia.org/wiki/Basic_block for a brief discussion of
18 : // basic blocks, their uses, and related terminology.
19 : //
20 : // TODO(rogerm): Unify the representation and idioms for attributes of
21 : // block, basic-blocks, and labels. Blocks and labels are similar but
22 : // not the same, and basic-blocks just has "is_padding" as a boolean.
23 :
24 : #ifndef SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_H_
25 : #define SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_H_
26 :
27 : #include "base/string_piece.h"
28 : #include "syzygy/block_graph/block_graph.h"
29 : #include "syzygy/common/align.h"
30 : #include "syzygy/core/assembler.h"
31 : #include "syzygy/core/disassembler_util.h"
32 :
33 : #include "distorm.h" // NOLINT
34 :
35 : namespace block_graph {
36 :
37 : // Forward declarations.
38 : class BasicBlock;
39 : class BasicCodeBlock;
40 : class BasicDataBlock;
41 : class Instruction;
42 : class Successor;
43 :
44 : // Represents a reference from one basic-block to another basic-block or to
45 : // another code- or data-block altogether.
46 : class BasicBlockReference {
47 : public:
48 : typedef BlockGraph::ReferenceType ReferenceType;
49 : typedef BlockGraph::Block Block;
50 : typedef BlockGraph::Offset Offset;
51 : typedef BlockGraph::Size Size;
52 :
53 : enum ReferredType {
54 : REFERRED_TYPE_UNKNOWN,
55 : REFERRED_TYPE_BLOCK,
56 : REFERRED_TYPE_BASIC_BLOCK,
57 :
58 : // This enum value should always be last.
59 : MAX_REFERRED_TYPE,
60 : };
61 :
62 : // Default constructor; needed for storage in stl containers.
63 : BasicBlockReference();
64 :
65 : // Create a reference to a block.
66 : //
67 : // @param type type of reference.
68 : // @param size size of reference.
69 : // @param block the referenced block.
70 : // @param offset offset of reference into @p block.
71 : // @param base base of the reference within @p block.
72 : BasicBlockReference(ReferenceType type,
73 : Size size,
74 : Block* block,
75 : Offset offset,
76 : Offset base);
77 :
78 : // Create a reference to a basic-block.
79 : //
80 : // @param type type of reference.
81 : // @param size size of reference.
82 : // @param basic_block the referenced basic block.
83 : BasicBlockReference(ReferenceType type,
84 : Size size,
85 : BasicBlock* basic_block);
86 :
87 : // Creates a reference to the same destination as @p ref, but with
88 : // a potentially new type and size.
89 : //
90 : // @param type type of reference.
91 : // @param size size of reference.
92 : // @param basic_block the destination for the new reference.
93 : BasicBlockReference(ReferenceType type,
94 : Size size,
95 : const BasicBlockReference& ref);
96 :
97 : // Copy constructor.
98 : BasicBlockReference(const BasicBlockReference& other);
99 :
100 : // Accessors.
101 : // @{
102 :
103 : // Retrieves the type of block (macro or basic) that it referenced.
104 E : ReferredType referred_type() const { return referred_type_; }
105 :
106 : // Retrieves the type reference (absolute or relative) for this reference.
107 E : ReferenceType reference_type() const { return reference_type_; }
108 :
109 : // Retrieves the size of the reference.
110 E : Size size() const { return size_; }
111 :
112 : // Retrieves the referenced block or NULL if this reference does not
113 : // refer to a block.
114 E : const Block* block() const {
115 E : return referred_type_ == REFERRED_TYPE_BLOCK ? referred_block_ : NULL;
116 E : }
117 :
118 : // Retrieves the referenced block or NULL if this reference does not
119 : // refer to a block.
120 E : Block* block() {
121 E : return referred_type_ == REFERRED_TYPE_BLOCK ? referred_block_ : NULL;
122 E : }
123 :
124 : // Retrieves the referenced basic-block or NULL if this reference does not
125 : // refer to a basic block.
126 E : const BasicBlock* basic_block() const {
127 : return referred_type_ == REFERRED_TYPE_BASIC_BLOCK ?
128 E : referred_basic_block_ : NULL;
129 E : }
130 :
131 : // Retrieves the referenced basic-block or NULL if this reference does not
132 : // refer to a basic block.
133 E : BasicBlock* basic_block() {
134 : return referred_type_ == REFERRED_TYPE_BASIC_BLOCK ?
135 E : referred_basic_block_ : NULL;
136 E : }
137 :
138 : // Retrieves the offset into the referenced macro- or basic-block.
139 E : Offset offset() const { return offset_; }
140 :
141 : // Retrieves the base offset to which this reference refers.
142 E : Offset base() const { return base_; }
143 : // @}
144 :
145 : // Compare this BasicBlockReferences with another for equality.
146 E : bool operator==(const BasicBlockReference& other) const {
147 : return (referred_type_ == other.referred_type_ &&
148 : reference_type_ == other.reference_type_ &&
149 : size_ == other.size_ &&
150 : referred_block_ == other.referred_block_ &&
151 E : offset_ == other.offset_);
152 E : }
153 :
154 : // Test if this reference has been initialized to refer to something.
155 E : bool IsValid() const {
156 E : return size_ != 0 && referred_block_ != NULL;
157 E : }
158 :
159 : protected:
160 : // Denotes whether this reference is to a block or basic block.
161 : ReferredType referred_type_;
162 :
163 : // The type of this reference.
164 : ReferenceType reference_type_;
165 :
166 : // The size of this reference.
167 : // Absolute references are always pointer wide, but PC-relative
168 : // references can be 1, 2 or 4 bytes wide, which affects their range.
169 : Size size_;
170 :
171 : // The block or basic-block that is referenced.
172 : union {
173 : Block* referred_block_;
174 : BasicBlock* referred_basic_block_;
175 : };
176 :
177 : // The offset into the referenced block or basic-block. This may or may not
178 : // end up referring into the target block's byte range.
179 : Offset offset_;
180 :
181 : // The base of the reference, as an offset into the referenced block or
182 : // basic-block. This must be a location strictly within the target block's
183 : // byte range.
184 : Offset base_;
185 : };
186 :
187 : // This class keeps track of a reference from an external block to a basic
188 : // block. Instances of this only make sense in the context of a given basic
189 : // block breakdown.
190 : class BasicBlockReferrer {
191 : public:
192 : typedef BlockGraph::Block Block;
193 : typedef BlockGraph::Offset Offset;
194 :
195 : // Create an empty (invalid) BasicBlockReferrer.
196 : BasicBlockReferrer();
197 :
198 : // Create a BasicBlockReferrer which tracks that an external block makes
199 : // reference to this basic block.
200 : // @param block The block which refers to this basic block.
201 : // @param offset The offset in the block at which the reference occurs.
202 : BasicBlockReferrer(const Block* block, Offset offset);
203 :
204 : // Create a copy of the @p other BasicBlockReferrer.
205 : // @param other A basic block referrer record to be copy constructed.
206 : BasicBlockReferrer(const BasicBlockReferrer& other);
207 :
208 : // Returns the block which refers to this basic block, or NULL.
209 E : const Block* block() const {
210 E : return referrer_;
211 E : }
212 :
213 : // Returns the offset in the referrer at which the reference to
214 : // the basic block occurs.
215 E : Offset offset() const { return offset_; }
216 :
217 : // Returns whether or not this is a valid basic block referrer object.
218 : bool IsValid() const;
219 :
220 : // Equality comparator.
221 E : bool operator==(const BasicBlockReferrer& other) const {
222 E : return referrer_ == other.referrer_ && offset_ == other.offset_;
223 E : }
224 :
225 : // Less-than comparator. Useful for putting BasicBlockReferrers into
226 : // ordered containers.
227 : struct CompareAsLess {
228 : bool operator()(const BasicBlockReferrer& lhs,
229 E : const BasicBlockReferrer& rhs) const {
230 : return lhs.referrer_ < rhs.referrer_ ||
231 E : (lhs.referrer_ == rhs.referrer_ && lhs.offset_ < rhs.offset_);
232 E : }
233 : };
234 :
235 : protected:
236 : // The referring block.
237 : const Block* referrer_;
238 :
239 : // The source offset in the block where the reference occurs.
240 : Offset offset_;
241 : };
242 :
243 : // Represents an instruction in a basic-block.
244 : class Instruction {
245 : public:
246 : typedef BlockGraph::Size Size;
247 : typedef BlockGraph::Offset Offset;
248 : typedef BlockGraph::Block::SourceRange SourceRange;
249 : typedef _DInst Representation;
250 : typedef std::map<Offset, BasicBlockReference> BasicBlockReferenceMap;
251 :
252 : // The maximum size (in bytes) of an x86 instruction, per specs.
253 : static const size_t kMaxSize = core::AssemblerImpl::kMaxInstructionLength;
254 :
255 : // A default constructed Instruction will be a single byte NOP.
256 : Instruction();
257 :
258 : // Copy constructor.
259 : Instruction(const Instruction& other);
260 :
261 : // Factory to construct an initialized an Instruction instance from a buffer.
262 : // @param buf the data comprising the instruction.
263 : // @param len the maximum length (in bytes) of @p buf to consume
264 : // @returns true on success, false otherwise.
265 : static bool FromBuffer(const uint8* buf, size_t len, Instruction* inst);
266 :
267 : // Accessors.
268 : // @{
269 E : const Representation& representation() const { return representation_; }
270 E : Representation& representation() { return representation_; }
271 E : const BasicBlockReferenceMap& references() const { return references_; }
272 E : BasicBlockReferenceMap& references() { return references_; }
273 :
274 E : SourceRange source_range() const { return source_range_; }
275 E : void set_source_range(const SourceRange& source_range) {
276 E : source_range_ = source_range;
277 E : }
278 E : const BlockGraph::Label& label() const { return label_; }
279 E : void set_label(const BlockGraph::Label& label) { label_ = label; }
280 E : bool has_label() const { return label_.IsValid(); }
281 :
282 E : uint16 opcode() const { return representation_.opcode; }
283 E : Size size() const { return representation_.size; }
284 E : const uint8* data() const { return data_; }
285 : /// @}
286 :
287 : // @name Deprecated accessors.
288 : // @{
289 : Offset offset() const { return offset_; }
290 : void set_offset(Offset offset) { offset_ = offset; }
291 : // @}
292 :
293 : // @name Helper functions.
294 : // @{
295 E : bool IsNop() const { return core::IsNop(representation_); }
296 E : bool IsCall() const { return core::IsCall(representation_); }
297 E : bool IsReturn() const { return core::IsReturn(representation_); }
298 E : bool IsSystemCall() const { return core::IsSystemCall(representation_); }
299 E : bool IsConditionalBranch() const {
300 E : return core::IsConditionalBranch(representation_);
301 E : }
302 : bool IsUnconditionalBranch() const {
303 : return core::IsUnconditionalBranch(representation_);
304 : }
305 E : bool IsBranch() const { return core::IsBranch(representation_); }
306 E : bool HasPcRelativeOperand(int operand_index) const {
307 E : return core::HasPcRelativeOperand(representation_, operand_index);
308 E : }
309 E : bool IsControlFlow() const { return core::IsControlFlow(representation_); }
310 E : bool IsImplicitControlFlow() const {
311 E : return core::IsImplicitControlFlow(representation_);
312 E : }
313 : bool IsInterrupt() const { return core::IsInterrupt(representation_); }
314 : bool IsDebugInterrupt() const {
315 : return core::IsDebugInterrupt(representation_);
316 : }
317 : bool CallsNonReturningFunction() const;
318 : // @}
319 :
320 : // Returns the mnemonic name for this instruction.
321 : const char* GetName() const;
322 :
323 : // Dump a text representation of this instruction.
324 : // @param buf receives the text representation.
325 : // @returns true if this instruction was successfully dumped, false otherwise.
326 : bool ToString(std::string* buf) const;
327 :
328 : // Returns the maximum size required to serialize this instruction.
329 : Size GetMaxSize() const { return representation_.size; }
330 :
331 : // Add a reference @p ref to this instruction at @p offset. If the reference
332 : // is to a basic block, also update that basic blocks referrer set.
333 : bool SetReference(Offset offset, const BasicBlockReference& ref);
334 :
335 : // Finds the reference, if any, for @p operand_index of this instruction.
336 : // @param operand_index the desired operand, in the range 0-3.
337 : // @param reference on success returns the reference.
338 : // @returns true iff @p operand_index exists and has a reference.
339 : bool FindOperandReference(size_t operand_index,
340 : BasicBlockReference* reference) const;
341 :
342 : // Helper function to invert a conditional branching opcode.
343 : static bool InvertConditionalBranchOpcode(uint16* opcode);
344 :
345 : // Returns true if the given PC-relative or indirect-memory call instruction
346 : // is to a non-returning function. The block (and offset into it) being
347 : // directly referenced by the call need to be provided explicitly.
348 : static bool IsCallToNonReturningFunction(const Representation& inst,
349 : const BlockGraph::Block* target,
350 : Offset offset);
351 :
352 : protected:
353 : // Construct an instruction from its parsed representation and underlying
354 : // memory buffer.
355 : Instruction(const _DInst& repr, const uint8* data);
356 :
357 : // The internal representation of this instruction.
358 : Representation representation_;
359 :
360 : // Captures the references (if any) that this instruction makes to another
361 : // basic block or macro block.
362 : BasicBlockReferenceMap references_;
363 :
364 : // The label, if any, associated with this instruction.
365 : BlockGraph::Label label_;
366 :
367 : // The source range, if any, associated with this instruction.
368 : SourceRange source_range_;
369 :
370 : // The data associated with this instruction.
371 : uint8 data_[kMaxSize];
372 :
373 : // Deprecated.
374 : Offset offset_;
375 : };
376 :
377 : // This class represents a control flow transfer to a basic block, which
378 : // includes both the target basic block as well as the condition on which
379 : // control flows to that basic block.
380 : class Successor {
381 : public:
382 : typedef core::AbsoluteAddress AbsoluteAddress;
383 : typedef BlockGraph::Offset Offset;
384 : typedef BlockGraph::Size Size;
385 : typedef BlockGraph::Block::SourceRange SourceRange;
386 : typedef std::map<Offset, BasicBlockReference> BasicBlockReferenceMap;
387 :
388 : // The op-code of an binary instruction.
389 : typedef uint16 OpCode;
390 :
391 : // The set of logical branching flow a successor may embody.
392 : enum Condition {
393 : // Sentinel value denoting an invalid branch condition.
394 : kInvalidCondition = -1,
395 :
396 : // These correspond to the conditional branch instructions.
397 : // @{
398 : kConditionAbove = core::kAbove, // JA and JNBE.
399 : kConditionAboveOrEqual = core::kAboveEqual, // JAE, JNB and JNC.
400 : kConditionBelow = core::kBelow, // JB, JNAE and JC.
401 : kConditionBelowOrEqual = core::kBelowEqual, // JBE and JNA.
402 : kConditionEqual = core::kEqual, // JE and JZ.
403 : kConditionGreater = core::kGreater, // JG and JNLE.
404 : kConditionGreaterOrEqual = core::kGreaterEqual, // JGE and JNL.
405 : kConditionLess = core::kLess, // JL and JNGE.
406 : kConditionLessOrEqual = core::kLessEqual, // JLE and JNG.
407 : kConditionNotEqual = core::kNotEqual, // JNZ, JNE.
408 : kConditionNotOverflow = core::kNoOverflow, // JNO.
409 : kConditionNotParity = core::kParityOdd, // JNP and JPO.
410 : kConditionNotSigned = core::kNotSign, // JNS.
411 : kConditionOverflow = core::kOverflow, // JO.
412 : kConditionParity = core::kParityEven, // JP and JPE.
413 : kConditionSigned = core::kSign, // JS.
414 :
415 : // Definitions for the bounding values for the conditional branches.
416 : // Note: that the maximum must be defined here to let all subsequent
417 : // enum values be properly incremented.
418 : kMinConditionalBranch = core::kMinConditionCode,
419 : kMaxConditionalBranch = core::kMaxConditionCode,
420 :
421 : // Unconditional control flow instructions.
422 : // @{
423 : kConditionTrue, // JMP.
424 : // @}
425 :
426 : // Sentinels for the largest successor condition values.
427 : kMaxCondition,
428 : };
429 :
430 : // Constructors.
431 : // @{
432 :
433 : // Creates a dangling successor.
434 : //
435 : // This needs to exist so that successors can be stored in STL containers.
436 : Successor();
437 :
438 : // Creates a successor that resolves to a known block or basic block.
439 : //
440 : // @param condition the branching condition for this successor.
441 : // @param target the basic block to which this successor refers.
442 : // @param offset the offset in the original block at which the instruction(s)
443 : // for this successor are located.
444 : // @param size the length (in bytes) that the instructions for this successor
445 : // occupies in the original block.
446 : Successor(Condition condition,
447 : const BasicBlockReference& target,
448 : Size instruction_size);
449 :
450 : // Copy-constructor.
451 : Successor(const Successor& other);
452 : // @}
453 :
454 : // Accessors.
455 : // @{
456 : // The type of branch represented by this successor.
457 E : Condition condition() const { return condition_; }
458 :
459 E : BasicBlockReference reference() const { return reference_; }
460 E : void set_reference(const BasicBlockReference& reference) {
461 E : reference_ = reference;
462 E : };
463 :
464 E : SourceRange source_range() const { return source_range_; }
465 E : void set_source_range(const SourceRange& source_range) {
466 E : source_range_ = source_range;
467 E : }
468 E : Size instruction_size() const { return instruction_size_; }
469 E : const BlockGraph::Label& label() const { return label_; }
470 E : void set_label(const BlockGraph::Label& label) { label_ = label; }
471 E : bool has_label() const { return label_.IsValid(); }
472 : // @}
473 :
474 : // Set the target reference @p ref for this successor. If @p ref refers
475 : // to a basic block, also update that basic block's referrer set.
476 : bool SetReference(const BasicBlockReference& ref);
477 :
478 : // Get the branch type that corresponds to the given @p op_code.
479 : // @returns kInvalidCondition if @p op_code isn't a recognized branch
480 : // instruction.
481 : static Condition OpCodeToCondition(OpCode op_code);
482 :
483 : // Get the condition that represents the inversion of the given @p condition.
484 : //
485 : // @p condition the condition to invert.
486 : // @returns kInvalidCondition if @p condition is not invertible.
487 : static Condition InvertCondition(Condition condition);
488 :
489 : // Returns a textual description of this successor.
490 : std::string ToString() const;
491 :
492 : protected:
493 : // The type of branch represented by this successor.
494 : Condition condition_;
495 :
496 : // The destination for this successor.
497 : BasicBlockReference reference_;
498 :
499 : // The label, if any, associated with this successor.
500 : BlockGraph::Label label_;
501 :
502 : // The source range, if any, associated with this successor.
503 : SourceRange source_range_;
504 :
505 : // The size of the instruction this successor is derived from,
506 : // or zero if it's synthesized or added post-decomposition.
507 : Size instruction_size_;
508 : };
509 :
510 : // An indivisible portion of code or data within a code block.
511 : //
512 : // See http://en.wikipedia.org/wiki/Basic_block for a general description of
513 : // the properties. This has been augmented with the ability to also represent
514 : // blocks of data that are tightly coupled with the code (jump and case tables
515 : // for example).
516 : class BasicBlock {
517 : public:
518 : enum BasicBlockType {
519 : BASIC_CODE_BLOCK,
520 : BASIC_DATA_BLOCK,
521 :
522 : // This must be last.
523 : BASIC_BLOCK_TYPE_MAX
524 : };
525 :
526 : typedef BlockGraph::BlockId BlockId;
527 : typedef std::list<Instruction> Instructions;
528 : typedef BlockGraph::Size Size;
529 : typedef std::list<Successor> Successors;
530 : typedef BlockGraph::Offset Offset;
531 :
532 : // The collection of references this basic block makes to other basic
533 : // blocks, keyed by the references offset relative to the start of this
534 : // basic block.
535 : typedef Instruction::BasicBlockReferenceMap BasicBlockReferenceMap;
536 :
537 : // The set of the blocks that have a reference to this basic block.
538 : // This is keyed on block and source offset (not destination offset),
539 : // to allow us to easily locate and remove the back-references on change or
540 : // deletion.
541 : typedef std::set<BasicBlockReferrer, BasicBlockReferrer::CompareAsLess>
542 : BasicBlockReferrerSet;
543 :
544 : // This offset is used to denote that an instruction, successor, or
545 : // basic block has been synthesized and has no corresponding image in
546 : // the original block.
547 : static const Offset kNoOffset;
548 :
549 : // Virtual destructor to allow subclassing.
550 : virtual ~BasicBlock();
551 :
552 : // Return a textual label for a basic block type.
553 : static const char* BasicBlockTypeToString(BasicBlockType type);
554 :
555 : // Accessors.
556 : // @{
557 E : BasicBlockType type() const { return type_; }
558 E : const std::string& name() const { return name_; }
559 E : bool is_padding() const { return is_padding_; }
560 :
561 E : size_t alignment() const { return alignment_; }
562 E : void set_alignment(size_t alignment) {
563 E : DCHECK_LE(1u, alignment_);
564 E : DCHECK(common::IsPowerOfTwo(alignment));
565 E : alignment_ = alignment;
566 E : }
567 :
568 E : Offset offset() const { return offset_; }
569 E : void set_offset(Offset offset) { offset_ = offset; }
570 :
571 E : const BasicBlockReferrerSet& referrers() const { return referrers_; }
572 E : BasicBlockReferrerSet& referrers() { return referrers_; }
573 : // @}
574 :
575 : // Returns true iff this basic block is a valid block (i.e., it
576 : // is a BASIC_DATA_BLOCK the contains data XOR a BASIC_CODE_BLOCK that
577 : // contains instructions and/or successors.
578 : virtual bool IsValid() const = 0;
579 :
580 : // Mark this basic block as padding/unreachable. This transformation is uni-
581 : // directional; the block should be considered immutable once this is called.
582 : void MarkAsPadding();
583 :
584 : protected:
585 : // Initialize a basic block.
586 : // @param name A textual identifier for this basic block.
587 : // @param type The disposition (code, data, padding) of this basic block.
588 : BasicBlock(const base::StringPiece& name,
589 : BasicBlockType type);
590 :
591 : // The type of this basic block.
592 : BasicBlockType type_;
593 :
594 : // The name of this basic block.
595 : std::string name_;
596 :
597 : // The alignment of this basic block.
598 : size_t alignment_;
599 :
600 : // The offset of this basic block in the original block. Set to the offset
601 : // of the first byte the basic block originated from during decomposition.
602 : // Useful as a stable, unique identifier for basic blocks in a decomposition.
603 : Offset offset_;
604 :
605 : // The set of basic blocks references (from other basic blocks in same
606 : // original block) to this basic block.
607 : BasicBlockReferrerSet referrers_;
608 :
609 : // The label associated with this basic block.
610 : BlockGraph::Label label_;
611 :
612 : // Tracks whether or not this basic block is unreachable padding.
613 : bool is_padding_;
614 :
615 : private:
616 : DISALLOW_COPY_AND_ASSIGN(BasicBlock);
617 : };
618 :
619 : class BasicCodeBlock : public BasicBlock {
620 : public:
621 : // Initialize a basic code block.
622 : // @param name A textual identifier for this basic block.
623 : explicit BasicCodeBlock(const base::StringPiece& name);
624 :
625 : // Down-cast from basic block to basic code block.
626 : static BasicCodeBlock* Cast(BasicBlock* basic_block);
627 : static const BasicCodeBlock* Cast(const BasicBlock* basic_block);
628 :
629 : // Accessors.
630 : // @{
631 E : const Instructions& instructions() const { return instructions_; }
632 E : Instructions& instructions() { return instructions_; }
633 E : const Successors& successors() const { return successors_; }
634 E : Successors& successors() { return successors_; }
635 : // @}
636 :
637 : // Returns true iff this basic block is a valid code block - i.e., it
638 : // contains at least one instruction and/or 0-2 successors.
639 : virtual bool IsValid() const OVERRIDE;
640 :
641 : // Return the number of bytes required to store the instructions
642 : // this basic block contains, exclusive successors.
643 : Size GetInstructionSize() const;
644 :
645 : private:
646 : // The set of non-branching instructions comprising this basic-block.
647 : // Any branching at the end of the basic-block is represented using the
648 : // successors_ member.
649 : Instructions instructions_;
650 :
651 : // The set of (logical) successors to this basic block. There can only be
652 : // 0, 1 or 2 successors in this list.
653 : // If there is a single successor, it must be unconditional.
654 : // If there are two successors, they must have complementary conditions.
655 : Successors successors_;
656 :
657 : private:
658 : DISALLOW_COPY_AND_ASSIGN(BasicCodeBlock);
659 : };
660 :
661 : class BasicDataBlock : public BasicBlock {
662 : public:
663 : typedef BlockGraph::Block::SourceRange SourceRange;
664 :
665 : // Initialize a basic data or padding block.
666 : // @param name A textual identifier for this basic block.
667 : // @param type The disposition (data or padding) of this basic block.
668 : // @param data The block's data, must be non-NULL.
669 : // @param size The size of @p data, must be greater than zero.
670 : // @note The block does not take ownership of @p data, and @p data must have
671 : // a lifetime greater than the block.
672 : BasicDataBlock(const base::StringPiece& name,
673 : const uint8* data,
674 : Size size);
675 :
676 : // Down-cast from basic block to basic data block.
677 : static BasicDataBlock* Cast(BasicBlock* basic_block);
678 : static const BasicDataBlock* Cast(const BasicBlock* basic_block);
679 :
680 : // Accessors.
681 : // @{
682 E : Size size() const { return size_; }
683 E : const uint8* data() const { return data_; }
684 :
685 E : const BasicBlockReferenceMap& references() const { return references_; }
686 E : BasicBlockReferenceMap& references() { return references_; }
687 :
688 E : SourceRange source_range() const { return source_range_; }
689 E : void set_source_range(const SourceRange& source_range) {
690 E : source_range_ = source_range;
691 E : }
692 :
693 E : const BlockGraph::Label& label() const { return label_; }
694 E : void set_label(const BlockGraph::Label& label) { label_ = label; }
695 E : bool has_label() const { return label_.IsValid(); }
696 : // @}
697 :
698 : // Add a reference @p ref to this basic block at @p offset.
699 : bool SetReference(Offset offset, const BasicBlockReference& ref);
700 :
701 : // Returns true iff this basic block is a valid block i.e., it contains data.
702 : virtual bool IsValid() const OVERRIDE;
703 :
704 : private:
705 : // The number of bytes of data in the original block that corresponds with
706 : // this basic block.
707 : Size size_;
708 :
709 : // The data in the original block that corresponds with this basic block
710 : // will be referenced here.
711 : const uint8* data_;
712 :
713 : // The source range, if any, associated with this data block.
714 : SourceRange source_range_;
715 :
716 : // The map of references (if any) that this block makes to other basic blocks
717 : // from the original block.
718 : BasicBlockReferenceMap references_;
719 :
720 : private:
721 : DISALLOW_COPY_AND_ASSIGN(BasicDataBlock);
722 : };
723 :
724 : } // namespace block_graph
725 :
726 : #endif // SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_H_
|