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