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 : // Implements the Basic-Block Graph representation and APIs.
16 : //
17 : // Some notes on inverting the instructions that don't have a complement
18 : // in the instruction set.
19 : //
20 : // JCXZ/JECXZ:
21 : // The simplest might be to punt and not actually invert,
22 : // but trampoline. Otherwise, a truly inverted instruction sequence
23 : // would be something like.
24 : //
25 : // pushfd
26 : // cmp ecx, 0 ; Change to ecx as appropriate.
27 : // jnz fall-through
28 : // original-branch-target
29 : // popfd
30 : // ...
31 : //
32 : // fall-through;
33 : // popfd
34 : // ...
35 : //
36 : // Note that popfd is prepended to the instruction sequences of both
37 : // fall-through and original-branch-target. To represent this we
38 : // should introduce JCXNZ and JECXNZ pseudo-instructions to represent
39 : // this transformation, to allow the inversion to be reversible.
40 : //
41 : // LOOP/LOOPE/LOOPZ/LOOPNE/LOOPNZ:
42 : // The simplest would be to punt and not actually invert, but trampoline.
43 : // Otherwise, a truly inverted instruction sequence would be something
44 : // like (taking LOOPNZ/LOOPNE as an example)...
45 : //
46 : // pushfd
47 : // jnz pre-fall-through ; Switch to jz for LOOPZ, omit for LOOP.
48 : // dec cx
49 : // jnz fall-through
50 : // original-branch-target:
51 : // popfd
52 : // ...
53 : //
54 : // pre-fall-through:
55 : // dec cx ; Omit for LOOP.
56 : // fall-through:
57 : // popfd
58 : // ...
59 : //
60 : // Note that popfd is prepended onto the instruction sequences of both
61 : // fall-through and original-branch-target. To represent this we
62 : // should introduce pseudo instructions to represent each inversion,
63 : // which would allow the inversion to be reversible.
64 :
65 : #include "syzygy/block_graph/basic_block.h"
66 :
67 : #include <algorithm>
68 : #include <ostream>
69 :
70 : #include "base/stringprintf.h"
71 : #include "syzygy/core/assembler.h"
72 : #include "syzygy/core/disassembler_util.h"
73 :
74 : #include "mnemonics.h" // NOLINT
75 :
76 : namespace block_graph {
77 :
78 : namespace {
79 :
80 : // A list of printable names corresponding to basic block types. This needs to
81 : // be kept in sync with the BasicBlock::BasicBlockType enum!
82 : const char* kBasicBlockType[] = {
83 : "BASIC_CODE_BLOCK",
84 : "BASIC_DATA_BLOCK",
85 : };
86 :
87 : COMPILE_ASSERT(arraysize(kBasicBlockType) == BasicBlock::BASIC_BLOCK_TYPE_MAX,
88 : kBasicBlockType_not_in_sync);
89 :
90 E : bool IsUnconditionalBranch(const Instruction& inst) {
91 E : return META_GET_FC(inst.representation().meta) == FC_UNC_BRANCH;
92 E : }
93 :
94 E : bool IsConditionalBranch(const Instruction& inst) {
95 E : return META_GET_FC(inst.representation().meta) == FC_CND_BRANCH;
96 E : }
97 :
98 : bool UpdateBasicBlockReferenceMap(BasicBlock::Size object_size,
99 : BasicBlock::BasicBlockReferenceMap* ref_map,
100 : BasicBlock::Offset offset,
101 E : const BasicBlockReference& ref) {
102 E : DCHECK(ref_map != NULL);
103 E : DCHECK(ref.IsValid());
104 E : DCHECK_LE(BasicBlock::kNoOffset, offset);
105 E : DCHECK_LE(offset + ref.size(), object_size);
106 :
107 : typedef BasicBlock::BasicBlockReferenceMap::iterator Iterator;
108 :
109 : // Attempt to perform the insertion, returning the insert location and
110 : // whether or not the value at the insert location has been set to ref.
111 : std::pair<Iterator, bool> result =
112 E : ref_map->insert(std::make_pair(offset, ref));
113 :
114 : #ifndef NDEBUG
115 : // Validate no overlap with the previous reference, if any.
116 E : if (result.first != ref_map->begin()) {
117 E : Iterator prev(result.first);
118 E : --prev;
119 : DCHECK_GE(static_cast<BasicBlock::Size>(offset),
120 E : prev->first + prev->second.size());
121 : }
122 :
123 : // Validate no overlap with the next reference, if any.
124 E : Iterator next(result.first);
125 E : ++next;
126 : DCHECK(next == ref_map->end() ||
127 E : static_cast<BasicBlock::Size>(next->first) >= offset + ref.size());
128 : #endif
129 :
130 : // If the value wasn't actually inserted, then update it.
131 E : if (!result.second) {
132 E : BasicBlockReference& old = result.first->second;
133 E : DCHECK_EQ(old.size(), ref.size());
134 E : DCHECK_EQ(old.reference_type(), ref.reference_type());
135 E : old = ref;
136 : }
137 :
138 E : return result.second;
139 E : }
140 :
141 : } // namespace
142 :
143 : BasicBlockReference::BasicBlockReference()
144 : : referred_type_(REFERRED_TYPE_UNKNOWN),
145 : reference_type_(BlockGraph::RELATIVE_REF),
146 : size_(0),
147 : referred_block_(NULL),
148 : offset_(BasicBlock::kNoOffset),
149 E : base_(BasicBlock::kNoOffset) {
150 E : }
151 :
152 :
153 : BasicBlockReference::BasicBlockReference(ReferenceType type,
154 : Size size,
155 : Block* block,
156 : Offset offset,
157 : Offset base)
158 : : referred_type_(REFERRED_TYPE_BLOCK),
159 : reference_type_(type),
160 : size_(size),
161 : referred_block_(block),
162 : offset_(offset),
163 E : base_(base) {
164 E : DCHECK(size == 1 || size == 2 || size == 4);
165 E : DCHECK(block != NULL);
166 E : DCHECK_LE(0, base);
167 E : DCHECK_LT(static_cast<size_t>(base), block->size());
168 E : }
169 :
170 : BasicBlockReference::BasicBlockReference(ReferenceType type,
171 : Size size,
172 : BasicBlock* basic_block)
173 : : referred_type_(REFERRED_TYPE_BASIC_BLOCK),
174 : reference_type_(type),
175 : size_(size),
176 : referred_basic_block_(basic_block),
177 : offset_(0),
178 E : base_(0) {
179 E : DCHECK(size == 1 || size == 4);
180 E : DCHECK(basic_block != NULL);
181 E : }
182 :
183 : BasicBlockReference::BasicBlockReference(ReferenceType type,
184 : Size size,
185 : const BasicBlockReference& ref)
186 : : referred_type_(ref.referred_type_),
187 : reference_type_(type),
188 : size_(size),
189 : referred_block_(ref.referred_block_),
190 : offset_(ref.offset_),
191 E : base_(ref.base_) {
192 E : DCHECK(size == 1 || size == 4);
193 E : }
194 :
195 : BasicBlockReference::BasicBlockReference(const BasicBlockReference& other)
196 : : referred_type_(other.referred_type_),
197 : reference_type_(other.reference_type_),
198 : size_(other.size_),
199 : referred_block_(other.referred_block_),
200 : offset_(other.offset_),
201 E : base_(other.base_) {
202 E : }
203 :
204 : BasicBlockReferrer::BasicBlockReferrer()
205 : : referrer_(NULL),
206 E : offset_(BasicBlock::kNoOffset) {
207 E : }
208 :
209 : BasicBlockReferrer::BasicBlockReferrer(const Block* block, Offset offset)
210 : : referrer_(block),
211 E : offset_(offset) {
212 E : DCHECK(block != NULL);
213 E : DCHECK_GE(offset, 0);
214 E : }
215 :
216 : BasicBlockReferrer::BasicBlockReferrer(const BasicBlockReferrer& other)
217 : : referrer_(other.referrer_),
218 E : offset_(other.offset_) {
219 E : }
220 :
221 E : bool BasicBlockReferrer::IsValid() const {
222 E : if (referrer_ == NULL)
223 E : return false;
224 :
225 E : return offset_ >= 0;
226 E : }
227 :
228 E : Instruction::Instruction() : offset_(BasicBlock::kNoOffset) {
229 : static const uint8 kNop[] = { 0x90 };
230 E : CHECK(core::DecodeOneInstruction(kNop, sizeof(kNop), &representation_));
231 E : DCHECK_EQ(sizeof(kNop), representation_.size);
232 E : ::memcpy(data_, kNop, representation_.size);
233 E : ::memset(data_ + sizeof(kNop), 0, sizeof(data_) - sizeof(kNop));
234 E : }
235 :
236 : Instruction::Instruction(const _DInst& repr, const uint8* data)
237 E : : representation_(repr), offset_(BasicBlock::kNoOffset) {
238 E : DCHECK_LT(repr.size, sizeof(data_));
239 E : DCHECK(data != NULL);
240 E : ::memcpy(data_, data, repr.size);
241 E : ::memset(data_ + repr.size, 0, sizeof(data_) - repr.size);
242 E : }
243 :
244 : Instruction::Instruction(const Instruction& other)
245 : : representation_(other.representation_),
246 : references_(other.references_),
247 : source_range_(other.source_range_),
248 : label_(other.label_),
249 E : offset_(BasicBlock::kNoOffset) {
250 E : ::memcpy(data_, other.data_, sizeof(data_));
251 E : }
252 :
253 E : bool Instruction::FromBuffer(const uint8* buf, size_t len, Instruction* inst) {
254 E : DCHECK(buf != NULL);
255 E : DCHECK_LT(0U, len);
256 E : DCHECK(inst != NULL);
257 :
258 E : _DInst repr = {};
259 E : if (!core::DecodeOneInstruction(buf, len, &repr))
260 i : return false;
261 :
262 E : *inst = Instruction(repr, buf);
263 E : return true;
264 E : }
265 :
266 i : const char* Instruction::GetName() const {
267 : // The mnemonics are defined as NUL terminated unsigned char arrays.
268 i : return reinterpret_cast<char*>(GET_MNEMONIC_NAME(representation_.opcode));
269 i : }
270 :
271 E : bool Instruction::ToString(std::string* buf) const {
272 E : DCHECK(buf != NULL);
273 : return core::InstructionToString(
274 E : this->representation(), this->data(), this->size(), buf);
275 E : }
276 :
277 E : bool Instruction::CallsNonReturningFunction() const {
278 : // Is this a call instruction?
279 E : if (META_GET_FC(representation_.meta) != FC_CALL)
280 i : return false;
281 :
282 : // Is the target something we can follow?
283 E : uint8 operand_type = representation_.ops[0].type;
284 E : if (operand_type != O_PC && operand_type != O_DISP)
285 i : return false;
286 :
287 : // Get the reference.
288 E : DCHECK_EQ(1U, references_.size());
289 E : const BasicBlockReference& ref = references_.begin()->second;
290 :
291 : // This can happen if the call is recursive to the currently decomposed
292 : // function calling ourselves. In this case the reference will be to another
293 : // basic-block that is a part of the same parent block.
294 E : if (ref.block() == NULL) {
295 i : DCHECK(ref.basic_block() != NULL);
296 i : return false;
297 : }
298 :
299 : // Check whether the referenced block is a non-returning function.
300 E : DCHECK_EQ(ref.offset(), ref.base());
301 E : DCHECK_EQ(BlockGraph::Reference::kMaximumSize, ref.size());
302 E : if (!IsCallToNonReturningFunction(representation_, ref.block(), ref.offset()))
303 E : return false;
304 :
305 : // If we got here, then this is a non-returning call.
306 E : return true;
307 E : }
308 :
309 E : bool Instruction::SetReference(Offset offset, const BasicBlockReference& ref) {
310 E : return UpdateBasicBlockReferenceMap(this->size(), &references_, offset, ref);
311 E : }
312 :
313 : bool Instruction::FindOperandReference(size_t operand_index,
314 E : BasicBlockReference* reference) const {
315 E : DCHECK(reference != NULL);
316 :
317 : // We walk backwards through the operands, and back up the operand
318 : // location by the size of each operand, until we're at ours.
319 E : size_t operand_location = representation_.size;
320 E : size_t i = 0;
321 E : for (i = arraysize(representation_.ops); i != operand_index; --i) {
322 E : switch (representation_.ops[i - 1].type) {
323 : case O_NONE:
324 : case O_REG:
325 i : break;
326 :
327 : case O_IMM:
328 : case O_IMM1:
329 : case O_IMM2:
330 : case O_PTR:
331 : case O_PC:
332 E : operand_location -= representation_.ops[i - 1].size / 8;
333 E : break;
334 :
335 : case O_SMEM:
336 : case O_MEM:
337 : case O_DISP:
338 E : operand_location -= representation_.dispSize / 8;
339 : break;
340 : }
341 E : }
342 E : DCHECK_EQ(i, operand_index);
343 :
344 : Instruction::BasicBlockReferenceMap::const_iterator
345 E : it(references_.find(operand_location));
346 :
347 E : if (it != references_.end()) {
348 E : *reference = it->second;
349 E : return true;
350 : }
351 :
352 E : return false;
353 E : }
354 :
355 E : bool Instruction::InvertConditionalBranchOpcode(uint16* opcode) {
356 E : DCHECK(opcode != NULL);
357 :
358 E : switch (*opcode) {
359 : default:
360 E : LOG(ERROR) << GET_MNEMONIC_NAME(*opcode) << " is not invertible.";
361 E : return false;
362 :
363 : case I_JA: // Equivalent to JNBE.
364 E : *opcode = I_JBE;
365 E : return true;
366 :
367 : case I_JAE: // Equivalent to JNB and JNC.
368 E : *opcode = I_JB;
369 E : return true;
370 :
371 : case I_JB: // Equivalent to JNAE and JC.
372 E : *opcode = I_JAE;
373 E : return true;
374 :
375 : case I_JBE: // Equivalent to JNA.
376 E : *opcode = I_JA;
377 E : return true;
378 :
379 : case I_JCXZ:
380 : case I_JECXZ:
381 : // TODO(rogerm): Inverting these is not quite as simple as inverting
382 : // the others. The simplest might be to punt and not actually invert,
383 : // but trampoline. Otherwise, a truly inverted instruction sequence
384 : // would be something like.
385 : //
386 : // pushfd
387 : // cmp ecx, 0 ; Change to ecx as appropriate.
388 : // jnz fall-through
389 : // original-branch-target
390 : // popfd
391 : // ...
392 : //
393 : // fall-through;
394 : // popfd
395 : // ...
396 : //
397 : // Note that popfd is prepended to the instruction sequences of both
398 : // fall-through and original-branch-target. To represent this we
399 : // should introduce JCXNZ and JECXNZ pseudo-instructions to represent
400 : // this transformation, to allow the inversion to be reversible.
401 E : LOG(ERROR) << "Inversion of " << GET_MNEMONIC_NAME(*opcode)
402 : << " is not supported.";
403 E : return false;
404 :
405 : case I_JG: // Equivalent to JNLE.
406 E : *opcode = I_JLE;
407 E : return true;
408 :
409 : case I_JGE: // Equivalent to JNL.
410 E : *opcode = I_JL;
411 E : return true;
412 :
413 : case I_JL: // Equivalent to I_JNGE.
414 E : *opcode = I_JGE;
415 E : return true;
416 :
417 : case I_JLE: // Equivalent to JNG.
418 E : *opcode = I_JG;
419 E : return true;
420 :
421 : case I_JNO:
422 E : *opcode = I_JO;
423 E : return true;
424 :
425 : case I_JNP: // Equivalent to JPO.
426 E : *opcode = I_JP;
427 E : return true;
428 :
429 : case I_JNS:
430 E : *opcode = I_JS;
431 E : return true;
432 :
433 : case I_JNZ: // Equivalent to JNE.
434 E : *opcode = I_JZ;
435 E : return true;
436 :
437 : case I_JO:
438 E : *opcode = I_JNO;
439 E : return true;
440 :
441 : case I_JP: // Equivalent to JPE.
442 E : *opcode = I_JNP;
443 E : return true;
444 :
445 : case I_JS:
446 E : *opcode = I_JNS;
447 E : return true;
448 :
449 : case I_JZ: // Equivalent to JE.
450 E : *opcode = I_JNZ;
451 E : return true;
452 :
453 : case I_LOOP:
454 : case I_LOOPNZ: // Equivalent to LOOPNE.
455 : case I_LOOPZ: // Equivalent to LOOPE
456 : // TODO(rogerm): Inverting these is not quite as simple as inverting
457 : // the others. The simplest would be to punt and not actually invert,
458 : // but trampoline. Otherwise, a truly inverted instruction sequence
459 : // would be something like, for Inverse(LOOPNZ), ...
460 : //
461 : // pushfd
462 : // jnz pre-fall-through ; Switch to jz for LOOPZ, omit for LOOP.
463 : // dec cx
464 : // jnz fall-through
465 : // original-branch-target:
466 : // popfd
467 : // ...
468 : //
469 : // pre-fall-through:
470 : // dec cx ; Omit for LOOP.
471 : // fall-through:
472 : // popfd
473 : // ...
474 : //
475 : // Note that popfd is prepended onto the instruction sequences of both
476 : // fall-through and original-branch-target. To represent this we
477 : // should introduce pesudo instructions to represent each inversion,
478 : // which would allow the inversion to be reversible.
479 E : LOG(ERROR) << "Inversion of " << GET_MNEMONIC_NAME(*opcode)
480 : << " is not supported.";
481 E : return false;
482 : }
483 E : }
484 :
485 : bool Instruction::IsCallToNonReturningFunction(const Representation& inst,
486 : const BlockGraph::Block* target,
487 E : Offset offset) {
488 E : DCHECK_EQ(FC_CALL, META_GET_FC(inst.meta));
489 E : DCHECK(target != NULL);
490 :
491 E : if (inst.ops[0].type != O_PC && inst.ops[0].type != O_DISP)
492 i : return false;
493 :
494 E : if (inst.ops[0].type == O_DISP) {
495 E : DCHECK(target->type() == BlockGraph::DATA_BLOCK);
496 :
497 : // There need not always be a reference here. This could be to a data
498 : // block whose contents will be filled in at runtime.
499 E : BlockGraph::Reference ref;
500 E : if (!target->GetReference(offset, &ref))
501 E : return false;
502 :
503 E : target = ref.referenced();
504 :
505 : // If this is a relative reference it must be to a data block (it's a PE
506 : // parsed structure pointing to an import name thunk). If it's absolute
507 : // then it must be pointing to a code block.
508 : DCHECK((ref.type() == BlockGraph::RELATIVE_REF &&
509 : target->type() == BlockGraph::DATA_BLOCK) ||
510 : (ref.type() == BlockGraph::ABSOLUTE_REF &&
511 E : target->type() == BlockGraph::CODE_BLOCK));
512 : }
513 :
514 E : if ((target->attributes() & BlockGraph::NON_RETURN_FUNCTION) == 0)
515 E : return false;
516 :
517 E : return true;
518 E : }
519 :
520 E : Successor::Condition Successor::OpCodeToCondition(Successor::OpCode op_code) {
521 E : switch (op_code) {
522 : default:
523 E : LOG(ERROR) << GET_MNEMONIC_NAME(op_code) << " is not a branch.";
524 E : return kInvalidCondition;
525 :
526 : case I_JA: // Equivalent to JNBE.
527 E : return kConditionAbove;
528 :
529 : case I_JAE: // Equivalent to JNB and JNC.
530 E : return kConditionAboveOrEqual;
531 :
532 : case I_JB: // Equivalent to JNAE and JC.
533 E : return kConditionBelow;
534 :
535 : case I_JBE: // Equivalent to JNA.
536 E : return kConditionBelowOrEqual;
537 :
538 : case I_JG: // Equivalent to JNLE.
539 E : return kConditionGreater;
540 :
541 : case I_JGE: // Equivalent to JNL.
542 E : return kConditionGreaterOrEqual;
543 :
544 : case I_JL: // Equivalent to I_JNGE.
545 E : return kConditionLess;
546 :
547 : case I_JLE: // Equivalent to JNG.
548 E : return kConditionLessOrEqual;
549 :
550 : case I_JMP:
551 E : return kConditionTrue;
552 :
553 : case I_JNO:
554 E : return kConditionNotOverflow;
555 :
556 : case I_JNP: // Equivalent to JPO.
557 E : return kConditionNotParity;
558 :
559 : case I_JNS:
560 E : return kConditionNotSigned;
561 :
562 : case I_JNZ: // Equivalent to JNE.
563 E : return kConditionNotEqual;
564 :
565 : case I_JO:
566 E : return kConditionOverflow;
567 :
568 : case I_JP: // Equivalent to JPE.
569 E : return kConditionParity;
570 :
571 : case I_JS:
572 E : return kConditionSigned;
573 :
574 : case I_JZ: // Equivalent to JE.
575 E : return kConditionEqual;
576 : }
577 E : }
578 :
579 : Successor::Successor()
580 E : : condition_(kInvalidCondition), instruction_size_(0) {
581 E : }
582 :
583 : Successor::Successor(Successor::Condition condition,
584 : const BasicBlockReference& target,
585 : Size instruction_size)
586 : : condition_(condition),
587 E : instruction_size_(instruction_size) {
588 E : DCHECK(condition != kInvalidCondition);
589 E : bool inserted = SetReference(target);
590 E : DCHECK(inserted);
591 E : }
592 :
593 : Successor::Successor(const Successor& other)
594 : : condition_(other.condition_),
595 : reference_(other.reference_),
596 : source_range_(other.source_range_),
597 : instruction_size_(other.instruction_size_),
598 E : label_(other.label_) {
599 E : }
600 :
601 E : Successor::Condition Successor::InvertCondition(Condition cond) {
602 E : DCHECK_LT(kInvalidCondition, cond);
603 E : DCHECK_LE(kMinConditionalBranch, cond);
604 E : DCHECK_GT(kMaxCondition, cond);
605 :
606 : // The conditional branches correspond exactly to those from core::Assembler.
607 E : if (cond <= kMaxConditionalBranch) {
608 : return static_cast<Condition>(
609 E : core::NegateConditionCode(static_cast<core::ConditionCode>(cond)));
610 : }
611 :
612 E : DCHECK_EQ(kConditionTrue, cond);
613 E : return kInvalidCondition;
614 E : }
615 :
616 E : bool Successor::SetReference(const BasicBlockReference& ref) {
617 E : bool inserted = !reference_.IsValid();
618 E : reference_ = ref;
619 E : return inserted;
620 E : }
621 :
622 i : std::string Successor::ToString() const {
623 i : switch (condition_) {
624 : case kConditionAbove: // Equivalent to JNBE.
625 i : return"JA";
626 :
627 : case kConditionAboveOrEqual: // Equivalent to JNB and JNC.
628 i : return "JAE";
629 :
630 : case kConditionBelow: // Equivalent to JNAE and JC.
631 i : return "JB";
632 :
633 : case kConditionBelowOrEqual: // Equivalent to JNA.
634 i : return "JBE";
635 :
636 : case kConditionGreater: // Equivalent to JNLE.
637 i : return "JG";
638 :
639 : case kConditionGreaterOrEqual: // Equivalent to JNL.
640 i : return "JGE";
641 :
642 : case kConditionLess: // Equivalent to JNGE.
643 i : return "JL";
644 :
645 : case kConditionLessOrEqual: // Equivalent to JNG.
646 i : return "JLE";
647 :
648 : case kConditionTrue:
649 i : return "JMP";
650 :
651 : case kConditionNotOverflow:
652 i : return "JNO";
653 :
654 : case kConditionNotParity: // Equivalent to JPO.
655 i : return "JNP";
656 :
657 : case kConditionNotSigned:
658 i : return "JNS";
659 :
660 : case kConditionNotEqual: // Equivalent to JNE.
661 i : return "JNZ";
662 :
663 : case kConditionOverflow:
664 i : return "JO";
665 :
666 : case kConditionParity: // Equivalent to JPE.
667 i : return "JP";
668 :
669 : case kConditionSigned:
670 i : return "JS";
671 :
672 : case kConditionEqual: // Equivalent to JE.
673 i : return "JZ";
674 : }
675 :
676 i : return "";
677 i : }
678 :
679 : const BasicBlock::Offset BasicBlock::kNoOffset = -1;
680 :
681 : BasicBlock::BasicBlock(const base::StringPiece& name,
682 : BasicBlock::BasicBlockType type)
683 : : name_(name.begin(), name.end()),
684 : alignment_(1),
685 : type_(type),
686 : offset_(kNoOffset),
687 E : is_padding_(false) {
688 E : }
689 :
690 E : BasicBlock::~BasicBlock() {
691 E : }
692 :
693 : const char* BasicBlock::BasicBlockTypeToString(
694 E : BasicBlock::BasicBlockType type) {
695 E : DCHECK_LE(BasicBlock::BASIC_CODE_BLOCK, type);
696 E : DCHECK_GT(BasicBlock::BASIC_BLOCK_TYPE_MAX, type);
697 E : return kBasicBlockType[type];
698 E : }
699 :
700 E : void BasicBlock::MarkAsPadding() {
701 E : is_padding_ = true;
702 E : }
703 :
704 : BasicCodeBlock::BasicCodeBlock(const base::StringPiece& name)
705 E : : BasicBlock(name, BASIC_CODE_BLOCK) {
706 E : }
707 :
708 E : BasicCodeBlock* BasicCodeBlock::Cast(BasicBlock* basic_block) {
709 E : if (basic_block == NULL)
710 E : return NULL;
711 E : if (basic_block->type() == BasicBlock::BASIC_CODE_BLOCK)
712 E : return static_cast<BasicCodeBlock*>(basic_block);
713 E : return NULL;
714 E : }
715 :
716 E : const BasicCodeBlock* BasicCodeBlock::Cast(const BasicBlock* basic_block) {
717 E : if (basic_block == NULL)
718 E : return NULL;
719 E : if (basic_block->type() == BasicBlock::BASIC_CODE_BLOCK)
720 E : return static_cast<const BasicCodeBlock*>(basic_block);
721 E : return NULL;
722 E : }
723 :
724 E : bool BasicCodeBlock::IsValid() const {
725 : #ifndef NDEBUG
726 E : Instructions::const_iterator it = instructions().begin();
727 E : for (; it != instructions().end(); ++it) {
728 E : if (IsConditionalBranch(*it) || IsUnconditionalBranch(*it))
729 i : return false;
730 E : }
731 : #endif
732 :
733 E : switch (successors_.size()) {
734 : case 0:
735 : // If the basic code block has no successors, we expect that it would
736 : // have instructions; otherwise, it doesn't need to exist. We would
737 : // also expect that it ends in control-flow change that we can't
738 : // necessarily trace statically (ie., RET or computed jump).
739 : // TODO(rogerm): Validate that this is really true?
740 : return instructions().size() != 0 &&
741 : (instructions().back().representation().opcode == I_RET ||
742 E : instructions().back().representation().opcode == I_JMP);
743 :
744 : case 1:
745 : // A basic code block having exactly one successor implies that the
746 : // successor is unconditional.
747 E : return successors().front().condition() == Successor::kConditionTrue;
748 :
749 : case 2:
750 : // A basic code block having exactly two successors implies that each
751 : // successor is the inverse of the other.
752 : return successors().front().condition() ==
753 E : Successor::InvertCondition(successors().back().condition());
754 :
755 : default:
756 : // Any other number of successors implies that the data is borked.
757 i : NOTREACHED();
758 i : return false;
759 : }
760 E : }
761 :
762 E : BasicBlock::Size BasicCodeBlock::GetInstructionSize() const {
763 : // Tally the size of the instructions.
764 E : Size data_size = 0;
765 E : Instructions::const_iterator instr_iter = instructions_.begin();
766 E : for (; instr_iter != instructions_.end(); ++instr_iter)
767 E : data_size += instr_iter->size();
768 :
769 E : return data_size;
770 E : }
771 :
772 : BasicDataBlock::BasicDataBlock(const base::StringPiece& name,
773 : const uint8* data,
774 : Size size)
775 : : BasicBlock(name, BasicBlock::BASIC_DATA_BLOCK),
776 : size_(size),
777 E : data_(data) {
778 E : DCHECK(data != NULL);
779 E : DCHECK_NE(0u, size);
780 E : }
781 :
782 E : BasicDataBlock* BasicDataBlock::Cast(BasicBlock* basic_block) {
783 E : if (basic_block == NULL)
784 E : return NULL;
785 E : if (basic_block->type() == BasicBlock::BASIC_DATA_BLOCK)
786 E : return static_cast<BasicDataBlock*>(basic_block);
787 E : return NULL;
788 E : }
789 :
790 E : const BasicDataBlock* BasicDataBlock::Cast(const BasicBlock* basic_block) {
791 E : if (basic_block == NULL)
792 E : return NULL;
793 E : if (basic_block->type() == BasicBlock::BASIC_DATA_BLOCK)
794 E : return static_cast<const BasicDataBlock*>(basic_block);
795 E : return NULL;
796 E : }
797 :
798 : bool BasicDataBlock::SetReference(
799 E : Offset offset, const BasicBlockReference& ref) {
800 E : DCHECK_NE(BasicBlock::BASIC_CODE_BLOCK, type_);
801 E : return UpdateBasicBlockReferenceMap(this->size(), &references_, offset, ref);
802 E : }
803 :
804 i : bool BasicDataBlock::IsValid() const {
805 i : return true;
806 i : }
807 :
808 : } // namespace block_graph
|