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 E : return referred_type_ == REFERRED_TYPE_BASIC_BLOCK ?
124 : 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 E : return (referred_type_ == other.referred_type_ &&
137 : reference_type_ == other.reference_type_ &&
138 : size_ == other.size_ &&
139 : referred_block_ == other.referred_block_ &&
140 : 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 E : return lhs.referrer_ < rhs.referrer_ ||
227 : (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 uint32_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_t* buf, uint32_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_t opcode() const { return representation_.opcode; }
279 E : Size size() const { return representation_.size; }
280 E : const uint8_t* data() const { return data_; }
281 : uint8_t* GetMutableData() { return data_; }
282 : /// @}
283 :
284 : // @name Helper functions.
285 : // @{
286 E : bool IsNop() const { return core::IsNop(representation_); }
287 E : bool IsCall() const { return core::IsCall(representation_); }
288 E : bool IsReturn() const { return core::IsReturn(representation_); }
289 E : bool IsSystemCall() const { return core::IsSystemCall(representation_); }
290 E : bool IsConditionalBranch() const {
291 E : return core::IsConditionalBranch(representation_);
292 E : }
293 : bool IsUnconditionalBranch() const {
294 : return core::IsUnconditionalBranch(representation_);
295 : }
296 E : bool IsBranch() const { return core::IsBranch(representation_); }
297 E : bool HasPcRelativeOperand(int operand_index) const {
298 E : return core::HasPcRelativeOperand(representation_, operand_index);
299 E : }
300 E : bool IsControlFlow() const { return core::IsControlFlow(representation_); }
301 E : bool IsImplicitControlFlow() const {
302 E : return core::IsImplicitControlFlow(representation_);
303 E : }
304 E : bool IsInterrupt() const { return core::IsInterrupt(representation_); }
305 : bool IsDebugInterrupt() const {
306 : return core::IsDebugInterrupt(representation_);
307 : }
308 : bool CallsNonReturningFunction() const;
309 : // @}
310 :
311 : // Returns the mnemonic name for this instruction.
312 : const char* GetName() const;
313 :
314 : // Dump a text representation of this instruction.
315 : // @param buf receives the text representation.
316 : // @returns true if this instruction was successfully dumped, false otherwise.
317 : bool ToString(std::string* buf) const;
318 :
319 : // Returns the maximum size required to serialize this instruction.
320 : Size GetMaxSize() const { return representation_.size; }
321 :
322 : // Add a reference @p ref to this instruction at @p offset. If the reference
323 : // is to a basic block, also update that basic blocks referrer set.
324 : bool SetReference(Offset offset, const BasicBlockReference& ref);
325 :
326 : // Finds the reference, if any, for @p operand_index of this instruction.
327 : // @param operand_index the desired operand, in the range 0-3.
328 : // @param reference on success returns the reference.
329 : // @returns true iff @p operand_index exists and has a reference.
330 : bool FindOperandReference(size_t operand_index,
331 : BasicBlockReference* reference) const;
332 :
333 : // Helper function to invert a conditional branching opcode.
334 : static bool InvertConditionalBranchOpcode(uint16_t* opcode);
335 :
336 : // Returns true if the given PC-relative or indirect-memory call instruction
337 : // is to a non-returning function. The block (and offset into it) being
338 : // directly referenced by the call need to be provided explicitly.
339 : static bool IsCallToNonReturningFunction(const Representation& inst,
340 : const BlockGraph::Block* target,
341 : Offset offset);
342 :
343 : // @returns the tags associated with this object.
344 E : TagSet& tags() { return tags_; }
345 E : const TagSet& tags() const { return tags_; }
346 :
347 : protected:
348 : // Construct an instruction from its parsed representation and underlying
349 : // memory buffer.
350 : Instruction(const _DInst& repr, const uint8_t* data);
351 :
352 : // The internal representation of this instruction.
353 : Representation representation_;
354 :
355 : // Captures the references (if any) that this instruction makes to another
356 : // basic block or macro block.
357 : BasicBlockReferenceMap references_;
358 :
359 : // The label, if any, associated with this instruction.
360 : BlockGraph::Label label_;
361 :
362 : // The source range, if any, associated with this instruction.
363 : SourceRange source_range_;
364 :
365 : // The data associated with this instruction.
366 : uint8_t data_[kMaxSize];
367 :
368 : // The tags that are applied to this object.
369 : TagSet tags_;
370 : };
371 :
372 : // This class represents a control flow transfer to a basic block, which
373 : // includes both the target basic block as well as the condition on which
374 : // control flows to that basic block.
375 : class Successor {
376 : public:
377 : typedef core::AbsoluteAddress AbsoluteAddress;
378 : typedef BlockGraph::Offset Offset;
379 : typedef BlockGraph::Size Size;
380 : typedef BlockGraph::Block::SourceRange SourceRange;
381 : typedef std::map<Offset, BasicBlockReference> BasicBlockReferenceMap;
382 :
383 : // The op-code of an binary instruction.
384 : typedef uint16_t OpCode;
385 :
386 : // The set of logical branching flow a successor may embody.
387 : enum Condition {
388 : // Sentinel value denoting an invalid branch condition.
389 : kInvalidCondition = -1,
390 :
391 : // These correspond to the conditional branch instructions.
392 : // @{
393 : kConditionAbove = assm::kAbove, // JA and JNBE.
394 : kConditionAboveOrEqual = assm::kAboveEqual, // JAE, JNB and JNC.
395 : kConditionBelow = assm::kBelow, // JB, JNAE and JC.
396 : kConditionBelowOrEqual = assm::kBelowEqual, // JBE and JNA.
397 : kConditionEqual = assm::kEqual, // JE and JZ.
398 : kConditionGreater = assm::kGreater, // JG and JNLE.
399 : kConditionGreaterOrEqual = assm::kGreaterEqual, // JGE and JNL.
400 : kConditionLess = assm::kLess, // JL and JNGE.
401 : kConditionLessOrEqual = assm::kLessEqual, // JLE and JNG.
402 : kConditionNotEqual = assm::kNotEqual, // JNZ, JNE.
403 : kConditionNotOverflow = assm::kNoOverflow, // JNO.
404 : kConditionNotParity = assm::kParityOdd, // JNP and JPO.
405 : kConditionNotSigned = assm::kNotSign, // JNS.
406 : kConditionOverflow = assm::kOverflow, // JO.
407 : kConditionParity = assm::kParityEven, // JP and JPE.
408 : kConditionSigned = assm::kSign, // JS.
409 :
410 : // Definitions for the bounding values for the conditional branches.
411 : // Note: that the maximum must be defined here to let all subsequent
412 : // enum values be properly incremented.
413 : kMinConditionalBranch = assm::kMinConditionCode,
414 : kMaxConditionalBranch = assm::kMaxConditionCode,
415 :
416 : // Unconditional control flow instructions.
417 : // @{
418 : kConditionTrue, // JMP.
419 : // @}
420 :
421 : // Sentinels for the largest successor condition values.
422 : kMaxCondition,
423 : };
424 :
425 : // Constructors.
426 : // @{
427 :
428 : // Creates a dangling successor.
429 : //
430 : // This needs to exist so that successors can be stored in STL containers.
431 : Successor();
432 :
433 : // Creates a successor that resolves to a known block or basic block.
434 : //
435 : // @param condition the branching condition for this successor.
436 : // @param target the basic block to which this successor refers.
437 : // @param offset the offset in the original block at which the instruction(s)
438 : // for this successor are located.
439 : // @param size the length (in bytes) that the instructions for this successor
440 : // occupies in the original block.
441 : Successor(Condition condition,
442 : const BasicBlockReference& target,
443 : Size instruction_size);
444 :
445 : // Copy-constructor.
446 : Successor(const Successor& other);
447 : // @}
448 :
449 : // Accessors.
450 : // @{
451 : // The type of branch represented by this successor.
452 E : Condition condition() const { return condition_; }
453 :
454 E : BasicBlockReference reference() const { return reference_; }
455 E : void set_reference(const BasicBlockReference& reference) {
456 E : reference_ = reference;
457 E : }
458 :
459 E : SourceRange source_range() const { return source_range_; }
460 E : void set_source_range(const SourceRange& source_range) {
461 E : source_range_ = source_range;
462 E : }
463 E : Size instruction_size() const { return instruction_size_; }
464 E : const BlockGraph::Label& label() const { return label_; }
465 E : void set_label(const BlockGraph::Label& label) { label_ = label; }
466 E : bool has_label() const { return label_.IsValid(); }
467 : // @}
468 :
469 : // Set the target reference @p ref for this successor. If @p ref refers
470 : // to a basic block, also update that basic block's referrer set.
471 : bool SetReference(const BasicBlockReference& ref);
472 :
473 : // Get the branch type that corresponds to the given @p op_code.
474 : // @returns kInvalidCondition if @p op_code isn't a recognized branch
475 : // instruction.
476 : static Condition OpCodeToCondition(OpCode op_code);
477 :
478 : // Get the condition that represents the inversion of the given @p condition.
479 : //
480 : // @p condition the condition to invert.
481 : // @returns kInvalidCondition if @p condition is not invertible.
482 : static Condition InvertCondition(Condition condition);
483 :
484 : // Returns a textual description of this successor.
485 : std::string ToString() const;
486 :
487 : // @returns the tags associated with this object.
488 E : TagSet& tags() { return tags_; }
489 E : const TagSet& tags() const { return tags_; }
490 :
491 : protected:
492 : // The type of branch represented by this successor.
493 : Condition condition_;
494 :
495 : // The destination for this successor.
496 : BasicBlockReference reference_;
497 :
498 : // The label, if any, associated with this successor.
499 : BlockGraph::Label label_;
500 :
501 : // The source range, if any, associated with this successor.
502 : SourceRange source_range_;
503 :
504 : // The size of the instruction this successor is derived from,
505 : // or zero if it's synthesized or added post-decomposition.
506 : Size instruction_size_;
507 :
508 : // The tags that are applied to this object.
509 : TagSet tags_;
510 : };
511 :
512 : // An indivisible portion of code or data within a code block.
513 : //
514 : // See http://en.wikipedia.org/wiki/Basic_block for a general description of
515 : // the properties. This has been augmented with the ability to also represent
516 : // blocks of data that are tightly coupled with the code (jump and case tables
517 : // for example).
518 : class BasicBlock {
519 : public:
520 : enum BasicBlockType {
521 : BASIC_CODE_BLOCK,
522 : BASIC_DATA_BLOCK,
523 : BASIC_END_BLOCK,
524 :
525 : // This must be last.
526 : BASIC_BLOCK_TYPE_MAX
527 : };
528 :
529 : typedef BlockGraph::BlockId BlockId;
530 : typedef std::list<Instruction> Instructions;
531 : typedef BlockGraph::Size Size;
532 : typedef std::list<Successor> Successors;
533 : typedef BlockGraph::Offset Offset;
534 :
535 : // The collection of references this basic block makes to other basic
536 : // blocks, keyed by the references offset relative to the start of this
537 : // basic block.
538 : typedef Instruction::BasicBlockReferenceMap BasicBlockReferenceMap;
539 :
540 : // The set of the blocks that have a reference to this basic block.
541 : // This is keyed on block and source offset (not destination offset),
542 : // to allow us to easily locate and remove the back-references on change or
543 : // deletion.
544 : typedef std::set<BasicBlockReferrer, BasicBlockReferrer::CompareAsLess>
545 : BasicBlockReferrerSet;
546 :
547 : // This offset is used to denote that an instruction, successor, or
548 : // basic block has been synthesized and has no corresponding image in
549 : // the original block.
550 : static const Offset kNoOffset;
551 :
552 : // Virtual destructor to allow subclassing.
553 : virtual ~BasicBlock();
554 :
555 : // Return a textual label for a basic block type.
556 : static const char* BasicBlockTypeToString(BasicBlockType type);
557 :
558 : // Accessors.
559 : // @{
560 E : BlockId id() const { return id_; }
561 :
562 E : BasicBlockType type() const { return type_; }
563 E : const std::string& name() const { return name_; }
564 E : bool is_padding() const { return is_padding_; }
565 :
566 E : size_t alignment() const { return alignment_; }
567 E : void set_alignment(size_t alignment) {
568 E : DCHECK_LE(1u, alignment_);
569 E : DCHECK(common::IsPowerOfTwo(alignment));
570 E : alignment_ = alignment;
571 E : }
572 :
573 E : Offset offset() const { return offset_; }
574 E : void set_offset(Offset offset) { offset_ = offset; }
575 :
576 E : const BasicBlockReferrerSet& referrers() const { return referrers_; }
577 E : BasicBlockReferrerSet& referrers() { return referrers_; }
578 : // @}
579 :
580 : // Returns true iff this basic block is a valid block (i.e., it
581 : // is a BASIC_DATA_BLOCK the contains data XOR a BASIC_CODE_BLOCK that
582 : // contains instructions and/or successors.
583 : virtual bool IsValid() const = 0;
584 :
585 : // Mark this basic block as padding/unreachable. This transformation is uni-
586 : // directional; the block should be considered immutable once this is called.
587 : void MarkAsPadding();
588 :
589 : // @returns the tags associated with this object.
590 E : TagSet& tags() { return tags_; }
591 E : const TagSet& tags() const { return tags_; }
592 :
593 : // @return the subgraph associated with this object
594 : BasicBlockSubGraph* subgraph() const { return subgraph_; }
595 :
596 : protected:
597 : // Initialize a basic block.
598 : // @param subgraph The subgraph that owns this basic block.
599 : // @param name A textual identifier for this basic block.
600 : // @param id The unique identifier for this basic block.
601 : // @param type The disposition (code, data, padding) of this basic block.
602 : BasicBlock(BasicBlockSubGraph* subgraph,
603 : const base::StringPiece& name,
604 : BlockId id,
605 : BasicBlockType type);
606 :
607 : // The unique id for this basic block.
608 : BlockId id_;
609 :
610 : // The type of this basic block.
611 : BasicBlockType type_;
612 :
613 : // The name of this basic block.
614 : std::string name_;
615 :
616 : // The alignment of this basic block.
617 : size_t alignment_;
618 :
619 : // The offset of this basic block in the original block. Set to the offset
620 : // of the first byte the basic block originated from during decomposition.
621 : // Useful as a stable, unique identifier for basic blocks in a decomposition.
622 : Offset offset_;
623 :
624 : // The set of blocks that reference this basic block. This is exclusive
625 : // of references from other basic blocks, e.g. references from the block
626 : // (or blocks) that are currently decomposed to basic blocks.
627 : BasicBlockReferrerSet referrers_;
628 :
629 : // The label associated with this basic block.
630 : BlockGraph::Label label_;
631 :
632 : // Tracks whether or not this basic block is unreachable padding.
633 : bool is_padding_;
634 :
635 : // The subgraph to which belongs this basic block.
636 : BasicBlockSubGraph* subgraph_;
637 :
638 : // The tags that are applied to this object.
639 : TagSet tags_;
640 :
641 : private:
642 : DISALLOW_COPY_AND_ASSIGN(BasicBlock);
643 : };
644 :
645 : class BasicCodeBlock : public BasicBlock {
646 : public:
647 : // Down-cast from basic block to basic code block.
648 : static BasicCodeBlock* Cast(BasicBlock* basic_block);
649 : static const BasicCodeBlock* Cast(const BasicBlock* basic_block);
650 :
651 : // Accessors.
652 : // @{
653 E : const Instructions& instructions() const { return instructions_; }
654 E : Instructions& instructions() { return instructions_; }
655 E : const Successors& successors() const { return successors_; }
656 E : Successors& successors() { return successors_; }
657 : // @}
658 :
659 : // Returns true iff this basic block is a valid code block - i.e., it
660 : // contains at least one instruction and/or 0-2 successors.
661 : bool IsValid() const override;
662 :
663 : // Return the number of bytes required to store the instructions
664 : // this basic block contains, exclusive successors.
665 : Size GetInstructionSize() const;
666 :
667 : private:
668 : // BasicBlockSubGraph has a factory for this type.
669 : friend class BasicBlockSubGraph;
670 :
671 : // Initialize a basic code block.
672 : // @param subgraph The subgraph to which belongs this basic block.
673 : // @param name A textual identifier for this basic block.
674 : // @param id The unique identifier representing this basic block.
675 : // @note This is protected so that basic-blocks may only be created via the
676 : // subgraph factory.
677 : BasicCodeBlock(BasicBlockSubGraph* subgraph, const base::StringPiece& name,
678 : BlockId id);
679 :
680 : // The set of non-branching instructions comprising this basic-block.
681 : // Any branching at the end of the basic-block is represented using the
682 : // successors_ member.
683 : Instructions instructions_;
684 :
685 : // The set of (logical) successors to this basic block. There can only be
686 : // 0, 1 or 2 successors in this list.
687 : // If there is a single successor, it must be unconditional.
688 : // If there are two successors, they must have complementary conditions.
689 : Successors successors_;
690 :
691 : DISALLOW_COPY_AND_ASSIGN(BasicCodeBlock);
692 : };
693 :
694 : class BasicDataBlock : public BasicBlock {
695 : public:
696 : typedef BlockGraph::Block::SourceRange SourceRange;
697 :
698 : // Down-cast from basic block to basic data block.
699 : static BasicDataBlock* Cast(BasicBlock* basic_block);
700 : static const BasicDataBlock* Cast(const BasicBlock* basic_block);
701 :
702 : // Accessors.
703 : // @{
704 E : Size size() const { return size_; }
705 E : const uint8_t* data() const { return data_; }
706 :
707 E : const BasicBlockReferenceMap& references() const { return references_; }
708 E : BasicBlockReferenceMap& references() { return references_; }
709 :
710 E : SourceRange source_range() const { return source_range_; }
711 E : void set_source_range(const SourceRange& source_range) {
712 E : source_range_ = source_range;
713 E : }
714 :
715 E : const BlockGraph::Label& label() const { return label_; }
716 E : void set_label(const BlockGraph::Label& label) { label_ = label; }
717 E : bool has_label() const { return label_.IsValid(); }
718 : // @}
719 :
720 : // Add a reference @p ref to this basic block at @p offset.
721 : bool SetReference(Offset offset, const BasicBlockReference& ref);
722 :
723 : // Returns true iff this basic block is a valid block i.e., it contains data.
724 : bool IsValid() const override;
725 :
726 : private:
727 : // BasicBlockSubGraph has a factory for this type.
728 : friend class BasicBlockSubGraph;
729 :
730 : // Initialize a basic data or padding block.
731 : // @param subgraph The subgraph to which belongs this basic block.
732 : // @param name A textual identifier for this basic block.
733 : // @param id The unique identifier representing this block.
734 : // @param type The disposition (data or padding) of this basic block.
735 : // @param data The block's data, must be non-NULL.
736 : // @param size The size of @p data, must be greater than zero.
737 : // @note The block does not take ownership of @p data, and @p data must have
738 : // a lifetime greater than the block.
739 : // @note This is protected so that basic-blocks may only be created via the
740 : // subgraph factory.
741 : BasicDataBlock(BasicBlockSubGraph* subgraph,
742 : const base::StringPiece& name,
743 : BlockId id,
744 : const uint8_t* data,
745 : Size size);
746 :
747 : // The number of bytes of data in the original block that corresponds with
748 : // this basic block.
749 : Size size_;
750 :
751 : // The data in the original block that corresponds with this basic block
752 : // will be referenced here.
753 : const uint8_t* data_;
754 :
755 : // The source range, if any, associated with this data block.
756 : SourceRange source_range_;
757 :
758 : // The map of references (if any) that this block makes to other basic blocks
759 : // from the original block.
760 : BasicBlockReferenceMap references_;
761 :
762 : DISALLOW_COPY_AND_ASSIGN(BasicDataBlock);
763 : };
764 :
765 : // A basic end block acts as placeholder block representing beyond the end of
766 : // a block. It acts as a concrete object that allows references and labels to
767 : // be drawn beyond the end of a block, as is often the case with symbol
768 : // information.
769 : class BasicEndBlock : public BasicBlock {
770 : public:
771 : // Down-cast from basic block to basic end block.
772 : static BasicEndBlock* Cast(BasicBlock* basic_block);
773 : static const BasicEndBlock* Cast(const BasicBlock* basic_block);
774 :
775 : // Accessors and mutators.
776 : // @{
777 : // An end block always has no size, as it contributes no data to the block.
778 : // It is simply a placeholder for references and labels.
779 E : Size size() const { return 0; }
780 E : const BasicBlockReferenceMap& references() const { return references_; }
781 E : BasicBlockReferenceMap& references() { return references_; }
782 :
783 E : const BlockGraph::Label& label() const { return label_; }
784 E : void set_label(const BlockGraph::Label& label) { label_ = label; }
785 E : bool has_label() const { return label_.IsValid(); }
786 : // @}
787 :
788 : // Add a reference @p ref to this basic block.
789 : bool SetReference(const BasicBlockReference& ref);
790 :
791 : // Returns true iff this basic block is a valid block.
792 : bool IsValid() const override;
793 :
794 : private:
795 : // BasicBlockSubGraph has a factory for this type.
796 : friend class BasicBlockSubGraph;
797 :
798 : // Initialize a basic data or padding block.
799 : // @param subgraph The subgraph to which belongs this basic block.
800 : // @param id The unique identifier representing this block.
801 : // @note This is protected so that basic-blocks may only be created via the
802 : // subgraph factory.
803 : BasicEndBlock(BasicBlockSubGraph* subgraph,
804 : BlockId id);
805 :
806 : // The map of references (if any) that this block makes to other basic blocks
807 : // from the original block.
808 : BasicBlockReferenceMap references_;
809 :
810 : DISALLOW_COPY_AND_ASSIGN(BasicEndBlock);
811 : };
812 :
813 : // Less-than comparator. Useful to keep ordered set stable.
814 : struct BasicBlockIdLess {
815 : bool operator()(const BasicBlock* lhs,
816 E : const BasicBlock* rhs) const {
817 E : DCHECK_NE(reinterpret_cast<const BasicBlock*>(NULL), lhs);
818 E : DCHECK_NE(reinterpret_cast<const BasicBlock*>(NULL), rhs);
819 E : return lhs->id() < rhs->id();
820 E : }
821 : };
822 :
823 : } // namespace block_graph
824 :
825 : #endif // SYZYGY_BLOCK_GRAPH_BASIC_BLOCK_H_
|