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 :
69 : #include "base/stringprintf.h"
70 : #include "syzygy/core/assembler.h"
71 : #include "syzygy/core/disassembler_util.h"
72 :
73 : #include "mnemonics.h" // NOLINT
74 :
75 : namespace block_graph {
76 :
77 : namespace {
78 :
79 : // A list of printable names corresponding to basic block types. This needs to
80 : // be kept in sync with the BasicBlock::BasicBlockType enum!
81 : const char* kBasicBlockType[] = {
82 : "BASIC_CODE_BLOCK",
83 : "BASIC_DATA_BLOCK",
84 : };
85 :
86 : COMPILE_ASSERT(arraysize(kBasicBlockType) == BasicBlock::BASIC_BLOCK_TYPE_MAX,
87 : kBasicBlockType_not_in_sync);
88 :
89 E : bool IsUnconditionalBranch(const Instruction& inst) {
90 E : return META_GET_FC(inst.representation().meta) == FC_UNC_BRANCH;
91 E : }
92 :
93 E : bool IsConditionalBranch(const Instruction& inst) {
94 E : return META_GET_FC(inst.representation().meta) == FC_CND_BRANCH;
95 E : }
96 :
97 : bool UpdateBasicBlockReferenceMap(BasicBlock::Size object_size,
98 : BasicBlock::BasicBlockReferenceMap* ref_map,
99 : BasicBlock::Offset offset,
100 E : const BasicBlockReference& ref) {
101 E : DCHECK(ref_map != NULL);
102 E : DCHECK(ref.IsValid());
103 E : DCHECK_LE(BasicBlock::kNoOffset, offset);
104 E : DCHECK_LE(offset + ref.size(), object_size);
105 :
106 : typedef BasicBlock::BasicBlockReferenceMap::iterator Iterator;
107 :
108 : // Attempt to perform the insertion, returning the insert location and
109 : // whether or not the value at the insert location has been set to ref.
110 : std::pair<Iterator, bool> result =
111 E : ref_map->insert(std::make_pair(offset, ref));
112 :
113 : #ifndef NDEBUG
114 : // Validate no overlap with the previous reference, if any.
115 E : if (result.first != ref_map->begin()) {
116 E : Iterator prev(result.first);
117 E : --prev;
118 : DCHECK_GE(static_cast<BasicBlock::Size>(offset),
119 E : prev->first + prev->second.size());
120 : }
121 :
122 : // Validate no overlap with the next reference, if any.
123 E : Iterator next(result.first);
124 E : ++next;
125 : DCHECK(next == ref_map->end() ||
126 E : static_cast<BasicBlock::Size>(next->first) >= offset + ref.size());
127 : #endif
128 :
129 : // If the value wasn't actually inserted, then update it.
130 E : if (!result.second) {
131 E : BasicBlockReference& old = result.first->second;
132 E : DCHECK_EQ(old.size(), ref.size());
133 E : DCHECK_EQ(old.reference_type(), ref.reference_type());
134 E : old = ref;
135 : }
136 :
137 E : return result.second;
138 E : }
139 :
140 : } // namespace
141 :
142 : BasicBlockReference::BasicBlockReference()
143 : : referred_type_(REFERRED_TYPE_UNKNOWN),
144 : reference_type_(BlockGraph::RELATIVE_REF),
145 : size_(0),
146 : referred_block_(NULL),
147 : offset_(BasicBlock::kNoOffset),
148 E : base_(BasicBlock::kNoOffset) {
149 E : }
150 :
151 : BasicBlockReference::BasicBlockReference(ReferenceType type,
152 : Size size,
153 : Block* block,
154 : Offset offset,
155 : Offset base)
156 : : referred_type_(REFERRED_TYPE_BLOCK),
157 : reference_type_(type),
158 : size_(size),
159 : referred_block_(block),
160 : offset_(offset),
161 E : base_(base) {
162 E : DCHECK(size == 1 || size == 2 || size == 4);
163 E : DCHECK(block != NULL);
164 E : DCHECK_LE(0, base);
165 E : DCHECK_LT(static_cast<size_t>(base), block->size());
166 E : }
167 :
168 : BasicBlockReference::BasicBlockReference(ReferenceType type,
169 : Size size,
170 : BasicBlock* basic_block)
171 : : referred_type_(REFERRED_TYPE_BASIC_BLOCK),
172 : reference_type_(type),
173 : size_(size),
174 : referred_basic_block_(basic_block),
175 : offset_(0),
176 E : base_(0) {
177 E : DCHECK(size == 1 || size == 4);
178 E : DCHECK(basic_block != NULL);
179 E : }
180 :
181 : BasicBlockReference::BasicBlockReference(ReferenceType type,
182 : Size size,
183 : const BasicBlockReference& ref)
184 : : referred_type_(ref.referred_type_),
185 : reference_type_(type),
186 : size_(size),
187 : referred_block_(ref.referred_block_),
188 : offset_(ref.offset_),
189 E : base_(ref.base_) {
190 E : DCHECK(size == 1 || size == 4);
191 E : }
192 :
193 : BasicBlockReference::BasicBlockReference(const BasicBlockReference& other)
194 : : referred_type_(other.referred_type_),
195 : reference_type_(other.reference_type_),
196 : size_(other.size_),
197 : referred_block_(other.referred_block_),
198 : offset_(other.offset_),
199 : base_(other.base_),
200 E : tags_(other.tags_) {
201 E : }
202 :
203 : BasicBlockReferrer::BasicBlockReferrer()
204 : : referrer_(NULL),
205 E : offset_(BasicBlock::kNoOffset) {
206 E : }
207 :
208 : BasicBlockReferrer::BasicBlockReferrer(const Block* block, Offset offset)
209 : : referrer_(block),
210 E : offset_(offset) {
211 E : DCHECK(block != NULL);
212 E : DCHECK_GE(offset, 0);
213 E : }
214 :
215 : BasicBlockReferrer::BasicBlockReferrer(const BasicBlockReferrer& other)
216 : : referrer_(other.referrer_),
217 E : offset_(other.offset_) {
218 E : }
219 :
220 E : bool BasicBlockReferrer::IsValid() const {
221 E : if (referrer_ == NULL)
222 E : return false;
223 :
224 E : return offset_ >= 0;
225 E : }
226 :
227 E : Instruction::Instruction() : offset_(BasicBlock::kNoOffset) {
228 : static const uint8 kNop[] = { 0x90 };
229 E : CHECK(core::DecodeOneInstruction(kNop, sizeof(kNop), &representation_));
230 E : DCHECK_EQ(sizeof(kNop), representation_.size);
231 E : ::memcpy(data_, kNop, representation_.size);
232 E : ::memset(data_ + sizeof(kNop), 0, sizeof(data_) - sizeof(kNop));
233 E : }
234 :
235 : Instruction::Instruction(const _DInst& repr, const uint8* data)
236 E : : representation_(repr), offset_(BasicBlock::kNoOffset) {
237 E : DCHECK_LT(repr.size, sizeof(data_));
238 E : DCHECK(data != NULL);
239 E : ::memcpy(data_, data, repr.size);
240 E : ::memset(data_ + repr.size, 0, sizeof(data_) - repr.size);
241 E : }
242 :
243 : Instruction::Instruction(const Instruction& other)
244 : : representation_(other.representation_),
245 : references_(other.references_),
246 : source_range_(other.source_range_),
247 : label_(other.label_),
248 : offset_(BasicBlock::kNoOffset),
249 E : tags_(other.tags_) {
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 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 pseudo 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 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 : label_(other.label_),
599 E : tags_(other.tags_) {
600 E : }
601 :
602 E : Successor::Condition Successor::InvertCondition(Condition cond) {
603 E : DCHECK_LT(kInvalidCondition, cond);
604 E : DCHECK_LE(kMinConditionalBranch, cond);
605 E : DCHECK_GT(kMaxCondition, cond);
606 :
607 : // The conditional branches correspond exactly to those from core::Assembler.
608 E : if (cond <= kMaxConditionalBranch) {
609 : return static_cast<Condition>(
610 E : core::NegateConditionCode(static_cast<core::ConditionCode>(cond)));
611 : }
612 :
613 E : DCHECK_EQ(kConditionTrue, cond);
614 E : return kInvalidCondition;
615 E : }
616 :
617 E : bool Successor::SetReference(const BasicBlockReference& ref) {
618 E : bool inserted = !reference_.IsValid();
619 E : reference_ = ref;
620 E : return inserted;
621 E : }
622 :
623 i : std::string Successor::ToString() const {
624 i : switch (condition_) {
625 : case kConditionAbove: // Equivalent to JNBE.
626 i : return"JA";
627 :
628 : case kConditionAboveOrEqual: // Equivalent to JNB and JNC.
629 i : return "JAE";
630 :
631 : case kConditionBelow: // Equivalent to JNAE and JC.
632 i : return "JB";
633 :
634 : case kConditionBelowOrEqual: // Equivalent to JNA.
635 i : return "JBE";
636 :
637 : case kConditionGreater: // Equivalent to JNLE.
638 i : return "JG";
639 :
640 : case kConditionGreaterOrEqual: // Equivalent to JNL.
641 i : return "JGE";
642 :
643 : case kConditionLess: // Equivalent to JNGE.
644 i : return "JL";
645 :
646 : case kConditionLessOrEqual: // Equivalent to JNG.
647 i : return "JLE";
648 :
649 : case kConditionTrue:
650 i : return "JMP";
651 :
652 : case kConditionNotOverflow:
653 i : return "JNO";
654 :
655 : case kConditionNotParity: // Equivalent to JPO.
656 i : return "JNP";
657 :
658 : case kConditionNotSigned:
659 i : return "JNS";
660 :
661 : case kConditionNotEqual: // Equivalent to JNE.
662 i : return "JNZ";
663 :
664 : case kConditionOverflow:
665 i : return "JO";
666 :
667 : case kConditionParity: // Equivalent to JPE.
668 i : return "JP";
669 :
670 : case kConditionSigned:
671 i : return "JS";
672 :
673 : case kConditionEqual: // Equivalent to JE.
674 i : return "JZ";
675 : }
676 :
677 i : return "";
678 i : }
679 :
680 : const BasicBlock::Offset BasicBlock::kNoOffset = -1;
681 :
682 : BasicBlock::BasicBlock(BasicBlockSubGraph* subgraph,
683 : const base::StringPiece& name,
684 : BlockId id,
685 : BasicBlock::BasicBlockType type)
686 : : subgraph_(subgraph),
687 : name_(name.begin(), name.end()),
688 : alignment_(1),
689 : id_(id),
690 : type_(type),
691 : offset_(kNoOffset),
692 E : is_padding_(false) {
693 E : DCHECK(subgraph_ != NULL);
694 E : }
695 :
696 E : BasicBlock::~BasicBlock() {
697 E : }
698 :
699 : const char* BasicBlock::BasicBlockTypeToString(
700 E : BasicBlock::BasicBlockType type) {
701 E : DCHECK_LE(BasicBlock::BASIC_CODE_BLOCK, type);
702 E : DCHECK_GT(BasicBlock::BASIC_BLOCK_TYPE_MAX, type);
703 E : return kBasicBlockType[type];
704 E : }
705 :
706 E : void BasicBlock::MarkAsPadding() {
707 E : is_padding_ = true;
708 E : }
709 :
710 : BasicCodeBlock::BasicCodeBlock(BasicBlockSubGraph* subgraph,
711 : const base::StringPiece& name,
712 : BlockId id)
713 E : : BasicBlock(subgraph, name, id, BASIC_CODE_BLOCK) {
714 E : }
715 :
716 E : BasicCodeBlock* BasicCodeBlock::Cast(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<BasicCodeBlock*>(basic_block);
721 E : return NULL;
722 E : }
723 :
724 E : const BasicCodeBlock* BasicCodeBlock::Cast(const BasicBlock* basic_block) {
725 E : if (basic_block == NULL)
726 E : return NULL;
727 E : if (basic_block->type() == BasicBlock::BASIC_CODE_BLOCK)
728 E : return static_cast<const BasicCodeBlock*>(basic_block);
729 E : return NULL;
730 E : }
731 :
732 E : bool BasicCodeBlock::IsValid() const {
733 : #ifndef NDEBUG
734 E : Instructions::const_iterator it = instructions().begin();
735 E : for (; it != instructions().end(); ++it) {
736 E : if (IsConditionalBranch(*it) || IsUnconditionalBranch(*it))
737 i : return false;
738 E : }
739 : #endif
740 :
741 E : switch (successors_.size()) {
742 : case 0:
743 : // If the basic code block has no successors, we expect that it would
744 : // have instructions; otherwise, it doesn't need to exist. We would
745 : // also expect that it ends in control-flow change that we can't
746 : // necessarily trace statically (ie., RET or computed jump).
747 : // TODO(rogerm): Validate that this is really true?
748 : return instructions().size() != 0 &&
749 : (instructions().back().representation().opcode == I_RET ||
750 E : instructions().back().representation().opcode == I_JMP);
751 :
752 : case 1:
753 : // A basic code block having exactly one successor implies that the
754 : // successor is unconditional.
755 E : return successors().front().condition() == Successor::kConditionTrue;
756 :
757 : case 2:
758 : // A basic code block having exactly two successors implies that each
759 : // successor is the inverse of the other.
760 : return successors().front().condition() ==
761 E : Successor::InvertCondition(successors().back().condition());
762 :
763 : default:
764 : // Any other number of successors implies that the data is borked.
765 i : NOTREACHED();
766 i : return false;
767 : }
768 E : }
769 :
770 E : BasicBlock::Size BasicCodeBlock::GetInstructionSize() const {
771 : // Tally the size of the instructions.
772 E : Size data_size = 0;
773 E : Instructions::const_iterator instr_iter = instructions_.begin();
774 E : for (; instr_iter != instructions_.end(); ++instr_iter)
775 E : data_size += instr_iter->size();
776 :
777 E : return data_size;
778 E : }
779 :
780 : BasicDataBlock::BasicDataBlock(BasicBlockSubGraph* subgraph,
781 : const base::StringPiece& name,
782 : BlockId id,
783 : const uint8* data,
784 : Size size)
785 : : BasicBlock(subgraph, name, id, BasicBlock::BASIC_DATA_BLOCK),
786 : size_(size),
787 E : data_(data) {
788 E : DCHECK(data != NULL);
789 E : DCHECK_NE(0u, size);
790 E : }
791 :
792 E : BasicDataBlock* BasicDataBlock::Cast(BasicBlock* basic_block) {
793 E : if (basic_block == NULL)
794 E : return NULL;
795 E : if (basic_block->type() == BasicBlock::BASIC_DATA_BLOCK)
796 E : return static_cast<BasicDataBlock*>(basic_block);
797 E : return NULL;
798 E : }
799 :
800 E : const BasicDataBlock* BasicDataBlock::Cast(const BasicBlock* basic_block) {
801 E : if (basic_block == NULL)
802 E : return NULL;
803 E : if (basic_block->type() == BasicBlock::BASIC_DATA_BLOCK)
804 E : return static_cast<const BasicDataBlock*>(basic_block);
805 E : return NULL;
806 E : }
807 :
808 : bool BasicDataBlock::SetReference(
809 E : Offset offset, const BasicBlockReference& ref) {
810 E : DCHECK_NE(BasicBlock::BASIC_CODE_BLOCK, type_);
811 E : return UpdateBasicBlockReferenceMap(this->size(), &references_, offset, ref);
812 E : }
813 :
814 i : bool BasicDataBlock::IsValid() const {
815 i : return true;
816 i : }
817 :
818 : } // namespace block_graph
|