diff options
| -rw-r--r-- | compiler/optimizing/code_sinking.cc | 64 |
1 files changed, 53 insertions, 11 deletions
diff --git a/compiler/optimizing/code_sinking.cc b/compiler/optimizing/code_sinking.cc index d759a16f48..33b5bd5169 100644 --- a/compiler/optimizing/code_sinking.cc +++ b/compiler/optimizing/code_sinking.cc @@ -16,6 +16,9 @@ #include "code_sinking.h" +#include <sstream> + +#include "android-base/logging.h" #include "base/arena_bit_vector.h" #include "base/array_ref.h" #include "base/bit_vector-inl.h" @@ -335,10 +338,6 @@ void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) { processed_instructions.ClearAllBits(); ArenaBitVector post_dominated(&allocator, graph_->GetBlocks().size(), /* expandable= */ false); post_dominated.ClearAllBits(); - ArenaBitVector instructions_that_can_move( - &allocator, number_of_instructions, /* expandable= */ false); - instructions_that_can_move.ClearAllBits(); - ScopedArenaVector<HInstruction*> move_in_order(allocator.Adapter(kArenaAllocMisc)); // Step (1): Visit post order to get a subset of blocks post dominated by `end_block`. // TODO(ngeoffray): Getting the full set of post-dominated should be done by @@ -411,6 +410,13 @@ void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) { HBasicBlock* common_dominator = finder.Get(); // Step (2): iterate over the worklist to find sinking candidates. + ArenaBitVector instructions_that_can_move( + &allocator, number_of_instructions, /* expandable= */ false); + instructions_that_can_move.ClearAllBits(); + ScopedArenaVector<ScopedArenaVector<HInstruction*>> instructions_to_move( + graph_->GetBlocks().size(), + ScopedArenaVector<HInstruction*>(allocator.Adapter(kArenaAllocMisc)), + allocator.Adapter(kArenaAllocMisc)); while (!worklist.empty()) { HInstruction* instruction = worklist.back(); if (processed_instructions.IsBitSet(instruction->GetId())) { @@ -467,7 +473,7 @@ void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) { // Instruction is a candidate for being sunk. Mark it as such, remove it from the // work list, and add its inputs to the work list. instructions_that_can_move.SetBit(instruction->GetId()); - move_in_order.push_back(instruction); + instructions_to_move[instruction->GetBlock()->GetBlockId()].push_back(instruction); processed_instructions.SetBit(instruction->GetId()); worklist.pop_back(); AddInputs(instruction, processed_instructions, post_dominated, &worklist); @@ -493,14 +499,50 @@ void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) { } } - // Make sure we process instructions in dominated order. This is required for heap - // stores. - std::sort(move_in_order.begin(), move_in_order.end(), [](HInstruction* a, HInstruction* b) { - return b->StrictlyDominates(a); - }); + // We want to process the instructions in reverse dominated order. This is required for heap + // stores. To guarantee this (including the transitivity of incomparability) we have some extra + // bookkeeping. + ScopedArenaVector<HInstruction*> instructions_to_move_sorted(allocator.Adapter(kArenaAllocMisc)); + for (HBasicBlock* block : graph_->GetPostOrder()) { + const int block_id = block->GetBlockId(); + + // Order the block itself first. + std::sort(instructions_to_move[block_id].begin(), + instructions_to_move[block_id].end(), + [&block](HInstruction* a, HInstruction* b) { + return block->GetInstructions().FoundBefore(b, a); + }); + + for (HInstruction* instruction : instructions_to_move[block_id]) { + instructions_to_move_sorted.push_back(instruction); + } + } + + if (kIsDebugBuild) { + // We should have ordered the instructions in reverse dominated order. This means that + // instructions shouldn't dominate instructions that come after it in the vector. + for (size_t i = 0; i < instructions_to_move_sorted.size(); ++i) { + for (size_t j = i + 1; j < instructions_to_move_sorted.size(); ++j) { + if (instructions_to_move_sorted[i]->StrictlyDominates(instructions_to_move_sorted[j])) { + std::stringstream ss; + graph_->Dump(ss, nullptr); + ss << "\n" + << "{"; + for (HInstruction* instr : instructions_to_move_sorted) { + ss << *instr << " in block: " << instr->GetBlock() << ", "; + } + ss << "}\n"; + ss << "i = " << i << " which is " << *instructions_to_move_sorted[i] + << "strictly dominates j = " << j << " which is " << *instructions_to_move_sorted[j] + << "\n"; + LOG(FATAL) << "Unexpected ordering of code sinking instructions: " << ss.str(); + } + } + } + } // Step (3): Try to move sinking candidates. - for (HInstruction* instruction : move_in_order) { + for (HInstruction* instruction : instructions_to_move_sorted) { HInstruction* position = nullptr; if (instruction->IsArraySet() || instruction->IsInstanceFieldSet() |