Add CFG and SSA form checkers in the optimizing compiler.
Checks performed on control-flow graphs:
- Ensure that the predecessors and successors of a basic block are
consistent within a control-flow graph.
- Ensure basic blocks end with a branch instruction.
- Detect phi functions listed in non-phi instruction lists and vice
versa.
- Ensure a block's instructions (and phi functions) are associated
with this very block.
Checks performed on SSA form graphs:
- Ensure an instruction dominates all its uses.
- Ensure there are no critical edges.
Change-Id: I1c12b4a61ecf608682152c897980ababa7eca847
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 207c605..7b5a78e 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -307,6 +307,14 @@
instruction->SetId(GetGraph()->GetNextInstructionId());
}
+void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial,
+ HInstruction* replacement) {
+ DCHECK(initial->GetBlock() == this);
+ InsertInstructionBefore(replacement, initial);
+ initial->ReplaceWith(replacement);
+ RemoveInstruction(initial);
+}
+
static void Add(HInstructionList* instruction_list,
HBasicBlock* block,
HInstruction* instruction) {
@@ -392,6 +400,54 @@
}
}
+bool HInstructionList::FoundBefore(const HInstruction* instruction1,
+ const HInstruction* instruction2) const {
+ DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock());
+ for (HInstructionIterator it(*this); !it.Done(); it.Advance()) {
+ if (it.Current() == instruction1) {
+ return true;
+ }
+ if (it.Current() == instruction2) {
+ return false;
+ }
+ }
+ LOG(FATAL) << "Did not find an order between two instructions of the same block.";
+ return true;
+}
+
+bool HInstruction::Dominates(HInstruction* other_instruction) const {
+ HBasicBlock* block = GetBlock();
+ HBasicBlock* other_block = other_instruction->GetBlock();
+ if (block != other_block) {
+ return GetBlock()->Dominates(other_instruction->GetBlock());
+ } else {
+ // If both instructions are in the same block, ensure this
+ // instruction comes before `other_instruction`.
+ if (IsPhi()) {
+ if (!other_instruction->IsPhi()) {
+ // Phis appear before non phi-instructions so this instruction
+ // dominates `other_instruction`.
+ return true;
+ } else {
+ // There is no order among phis.
+ LOG(FATAL) << "There is no dominance between phis of a same block.";
+ return false;
+ }
+ } else {
+ // `this` is not a phi.
+ if (other_instruction->IsPhi()) {
+ // Phis appear before non phi-instructions so this instruction
+ // does not dominate `other_instruction`.
+ return false;
+ } else {
+ // Check whether this instruction comes before
+ // `other_instruction` in the instruction list.
+ return block->GetInstructions().FoundBefore(this, other_instruction);
+ }
+ }
+ }
+}
+
void HInstruction::ReplaceWith(HInstruction* other) {
DCHECK(other != nullptr);
for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) {