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