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