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