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