diff options
44 files changed, 204 insertions, 196 deletions
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk index 76ee06e453..49887400f8 100644 --- a/build/Android.gtest.mk +++ b/build/Android.gtest.mk @@ -214,6 +214,8 @@ RUNTIME_GTEST_COMMON_SRC_FILES := \ runtime/base/stringprintf_test.cc \ runtime/base/time_utils_test.cc \ runtime/base/timing_logger_test.cc \ + runtime/base/transform_array_ref_test.cc \ + runtime/base/transform_iterator_test.cc \ runtime/base/variant_map_test.cc \ runtime/base/unix_file/fd_file_test.cc \ runtime/class_linker_test.cc \ @@ -308,9 +310,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \ compiler/utils/intrusive_forward_list_test.cc \ compiler/utils/string_reference_test.cc \ compiler/utils/swap_space_test.cc \ - compiler/utils/test_dex_file_builder_test.cc \ - compiler/utils/transform_array_ref_test.cc \ - compiler/utils/transform_iterator_test.cc \ + compiler/utils/test_dex_file_builder_test.cc COMPILER_GTEST_COMMON_SRC_FILES_all := \ compiler/jni/jni_cfi_test.cc \ diff --git a/compiler/compiled_method.h b/compiler/compiled_method.h index 2a81804f64..1a87448e80 100644 --- a/compiler/compiled_method.h +++ b/compiler/compiled_method.h @@ -23,10 +23,10 @@ #include <vector> #include "arch/instruction_set.h" +#include "base/array_ref.h" #include "base/bit_utils.h" #include "base/length_prefixed_array.h" #include "method_reference.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/debug/dwarf/headers.h b/compiler/debug/dwarf/headers.h index 146d9fddf5..28f108423e 100644 --- a/compiler/debug/dwarf/headers.h +++ b/compiler/debug/dwarf/headers.h @@ -19,13 +19,13 @@ #include <cstdint> +#include "base/array_ref.h" #include "debug/dwarf/debug_frame_opcode_writer.h" #include "debug/dwarf/debug_info_entry_writer.h" #include "debug/dwarf/debug_line_opcode_writer.h" #include "debug/dwarf/dwarf_constants.h" #include "debug/dwarf/register.h" #include "debug/dwarf/writer.h" -#include "utils/array_ref.h" namespace art { namespace dwarf { diff --git a/compiler/debug/elf_debug_writer.cc b/compiler/debug/elf_debug_writer.cc index 5bfdd16083..d1c10a9246 100644 --- a/compiler/debug/elf_debug_writer.cc +++ b/compiler/debug/elf_debug_writer.cc @@ -18,6 +18,7 @@ #include <vector> +#include "base/array_ref.h" #include "debug/dwarf/dwarf_constants.h" #include "debug/elf_compilation_unit.h" #include "debug/elf_debug_frame_writer.h" @@ -29,7 +30,6 @@ #include "debug/method_debug_info.h" #include "elf_builder.h" #include "linker/vector_output_stream.h" -#include "utils/array_ref.h" namespace art { namespace debug { diff --git a/compiler/debug/elf_debug_writer.h b/compiler/debug/elf_debug_writer.h index b0542c7ac6..07f7229827 100644 --- a/compiler/debug/elf_debug_writer.h +++ b/compiler/debug/elf_debug_writer.h @@ -19,11 +19,11 @@ #include <vector> +#include "base/array_ref.h" #include "base/macros.h" #include "base/mutex.h" #include "debug/dwarf/dwarf_constants.h" #include "elf_builder.h" -#include "utils/array_ref.h" namespace art { class OatHeader; diff --git a/compiler/driver/compiled_method_storage.h b/compiler/driver/compiled_method_storage.h index 8674abf815..124b5a6e25 100644 --- a/compiler/driver/compiled_method_storage.h +++ b/compiler/driver/compiled_method_storage.h @@ -20,9 +20,9 @@ #include <iosfwd> #include <memory> +#include "base/array_ref.h" #include "base/length_prefixed_array.h" #include "base/macros.h" -#include "utils/array_ref.h" #include "utils/dedupe_set.h" #include "utils/swap_space.h" diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc index c197ff918e..a149c07beb 100644 --- a/compiler/driver/compiler_driver.cc +++ b/compiler/driver/compiler_driver.cc @@ -26,6 +26,7 @@ #include "art_field-inl.h" #include "art_method-inl.h" +#include "base/array_ref.h" #include "base/bit_vector.h" #include "base/enums.h" #include "base/stl_util.h" @@ -67,7 +68,6 @@ #include "thread_pool.h" #include "trampolines/trampoline_compiler.h" #include "transaction.h" -#include "utils/array_ref.h" #include "utils/dex_cache_arrays_layout-inl.h" #include "utils/swap_space.h" #include "verifier/method_verifier.h" diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h index fbc1edd0ea..ee21efa854 100644 --- a/compiler/driver/compiler_driver.h +++ b/compiler/driver/compiler_driver.h @@ -24,6 +24,7 @@ #include "arch/instruction_set.h" #include "base/arena_allocator.h" +#include "base/array_ref.h" #include "base/bit_utils.h" #include "base/mutex.h" #include "base/timing_logger.h" @@ -39,7 +40,6 @@ #include "runtime.h" #include "safe_map.h" #include "thread_pool.h" -#include "utils/array_ref.h" #include "utils/dex_cache_arrays_layout.h" namespace art { diff --git a/compiler/elf_builder.h b/compiler/elf_builder.h index 7f2e1931d0..02831c9dc7 100644 --- a/compiler/elf_builder.h +++ b/compiler/elf_builder.h @@ -21,13 +21,13 @@ #include "arch/instruction_set.h" #include "arch/mips/instruction_set_features_mips.h" +#include "base/array_ref.h" #include "base/bit_utils.h" #include "base/casts.h" #include "base/unix_file/fd_file.h" #include "elf_utils.h" #include "leb128.h" #include "linker/error_delaying_output_stream.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/elf_writer.h b/compiler/elf_writer.h index c9ea0083d5..f8f91029d4 100644 --- a/compiler/elf_writer.h +++ b/compiler/elf_writer.h @@ -22,10 +22,10 @@ #include <string> #include <vector> +#include "base/array_ref.h" #include "base/macros.h" #include "base/mutex.h" #include "os.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/jni/quick/calling_convention.h b/compiler/jni/quick/calling_convention.h index 3d89146250..f541d8fa19 100644 --- a/compiler/jni/quick/calling_convention.h +++ b/compiler/jni/quick/calling_convention.h @@ -18,11 +18,11 @@ #define ART_COMPILER_JNI_QUICK_CALLING_CONVENTION_H_ #include "base/arena_object.h" +#include "base/array_ref.h" #include "base/enums.h" #include "handle_scope.h" #include "primitive.h" #include "thread.h" -#include "utils/array_ref.h" #include "utils/managed_register.h" namespace art { diff --git a/compiler/linker/arm64/relative_patcher_arm64.h b/compiler/linker/arm64/relative_patcher_arm64.h index 48ad1059b0..a4a80185dc 100644 --- a/compiler/linker/arm64/relative_patcher_arm64.h +++ b/compiler/linker/arm64/relative_patcher_arm64.h @@ -17,8 +17,8 @@ #ifndef ART_COMPILER_LINKER_ARM64_RELATIVE_PATCHER_ARM64_H_ #define ART_COMPILER_LINKER_ARM64_RELATIVE_PATCHER_ARM64_H_ +#include "base/array_ref.h" #include "linker/arm/relative_patcher_arm_base.h" -#include "utils/array_ref.h" namespace art { namespace linker { diff --git a/compiler/linker/relative_patcher.h b/compiler/linker/relative_patcher.h index a22b9f2c2d..15e955b2c6 100644 --- a/compiler/linker/relative_patcher.h +++ b/compiler/linker/relative_patcher.h @@ -21,9 +21,9 @@ #include "arch/instruction_set.h" #include "arch/instruction_set_features.h" +#include "base/array_ref.h" #include "base/macros.h" #include "method_reference.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/linker/relative_patcher_test.h b/compiler/linker/relative_patcher_test.h index d21f33e46f..304b31ca84 100644 --- a/compiler/linker/relative_patcher_test.h +++ b/compiler/linker/relative_patcher_test.h @@ -19,6 +19,7 @@ #include "arch/instruction_set.h" #include "arch/instruction_set_features.h" +#include "base/array_ref.h" #include "base/macros.h" #include "compiled_method.h" #include "dex/quick/dex_file_to_method_inliner_map.h" @@ -31,7 +32,6 @@ #include "method_reference.h" #include "oat.h" #include "oat_quick_method_header.h" -#include "utils/array_ref.h" #include "vector_output_stream.h" namespace art { diff --git a/compiler/oat_writer.h b/compiler/oat_writer.h index 77525f1a32..dd7d699eee 100644 --- a/compiler/oat_writer.h +++ b/compiler/oat_writer.h @@ -21,6 +21,7 @@ #include <cstddef> #include <memory> +#include "base/array_ref.h" #include "base/dchecked_vector.h" #include "linker/relative_patcher.h" // For linker::RelativePatcherTargetProvider. #include "mem_map.h" @@ -29,7 +30,6 @@ #include "oat.h" #include "os.h" #include "safe_map.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/optimizing/code_generator_arm.h b/compiler/optimizing/code_generator_arm.h index ce9d7e6056..38a2410f9a 100644 --- a/compiler/optimizing/code_generator_arm.h +++ b/compiler/optimizing/code_generator_arm.h @@ -556,10 +556,10 @@ class CodeGeneratorARM : public CodeGenerator { // artReadBarrierForRootSlow. void GenerateReadBarrierForRootSlow(HInstruction* instruction, Location out, Location root); - void GenerateNop(); + void GenerateNop() OVERRIDE; - void GenerateImplicitNullCheck(HNullCheck* instruction); - void GenerateExplicitNullCheck(HNullCheck* instruction); + void GenerateImplicitNullCheck(HNullCheck* instruction) OVERRIDE; + void GenerateExplicitNullCheck(HNullCheck* instruction) OVERRIDE; private: Register GetInvokeStaticOrDirectExtraParameter(HInvokeStaticOrDirect* invoke, Register temp); diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc index c00ab56a4c..599185acd3 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -448,7 +448,7 @@ class TypeCheckSlowPathARM64 : public SlowPathCodeARM64 { } const char* GetDescription() const OVERRIDE { return "TypeCheckSlowPathARM64"; } - bool IsFatal() const { return is_fatal_; } + bool IsFatal() const OVERRIDE { return is_fatal_; } private: const bool is_fatal_; diff --git a/compiler/optimizing/code_generator_arm64.h b/compiler/optimizing/code_generator_arm64.h index f0d79106dc..f1dc7eecb5 100644 --- a/compiler/optimizing/code_generator_arm64.h +++ b/compiler/optimizing/code_generator_arm64.h @@ -644,10 +644,10 @@ class CodeGeneratorARM64 : public CodeGenerator { // artReadBarrierForRootSlow. void GenerateReadBarrierForRootSlow(HInstruction* instruction, Location out, Location root); - void GenerateNop(); + void GenerateNop() OVERRIDE; - void GenerateImplicitNullCheck(HNullCheck* instruction); - void GenerateExplicitNullCheck(HNullCheck* instruction); + void GenerateImplicitNullCheck(HNullCheck* instruction) OVERRIDE; + void GenerateExplicitNullCheck(HNullCheck* instruction) OVERRIDE; private: using Uint64ToLiteralMap = ArenaSafeMap<uint64_t, vixl::aarch64::Literal<uint64_t>*>; diff --git a/compiler/optimizing/code_generator_mips.h b/compiler/optimizing/code_generator_mips.h index 956a466f9b..a42374f146 100644 --- a/compiler/optimizing/code_generator_mips.h +++ b/compiler/optimizing/code_generator_mips.h @@ -329,10 +329,10 @@ class CodeGeneratorMIPS : public CodeGenerator { void SetupBlockedRegisters() const OVERRIDE; - size_t SaveCoreRegister(size_t stack_index, uint32_t reg_id); - size_t RestoreCoreRegister(size_t stack_index, uint32_t reg_id); - size_t SaveFloatingPointRegister(size_t stack_index, uint32_t reg_id); - size_t RestoreFloatingPointRegister(size_t stack_index, uint32_t reg_id); + size_t SaveCoreRegister(size_t stack_index, uint32_t reg_id) OVERRIDE; + size_t RestoreCoreRegister(size_t stack_index, uint32_t reg_id) OVERRIDE; + size_t SaveFloatingPointRegister(size_t stack_index, uint32_t reg_id) OVERRIDE; + size_t RestoreFloatingPointRegister(size_t stack_index, uint32_t reg_id) OVERRIDE; void ClobberRA() { clobbered_ra_ = true; } @@ -363,7 +363,7 @@ class CodeGeneratorMIPS : public CodeGenerator { void MoveLocation(Location dst, Location src, Primitive::Type dst_type) OVERRIDE; - void MoveConstant(Location destination, int32_t value); + void MoveConstant(Location destination, int32_t value) OVERRIDE; void AddLocationAsTemp(Location location, LocationSummary* locations) OVERRIDE; @@ -375,7 +375,7 @@ class CodeGeneratorMIPS : public CodeGenerator { ParallelMoveResolver* GetMoveResolver() OVERRIDE { return &move_resolver_; } - bool NeedsTwoRegisters(Primitive::Type type) const { + bool NeedsTwoRegisters(Primitive::Type type) const OVERRIDE { return type == Primitive::kPrimLong; } @@ -403,9 +403,9 @@ class CodeGeneratorMIPS : public CodeGenerator { UNIMPLEMENTED(FATAL) << "Not implemented on MIPS"; } - void GenerateNop(); - void GenerateImplicitNullCheck(HNullCheck* instruction); - void GenerateExplicitNullCheck(HNullCheck* instruction); + void GenerateNop() OVERRIDE; + void GenerateImplicitNullCheck(HNullCheck* instruction) OVERRIDE; + void GenerateExplicitNullCheck(HNullCheck* instruction) OVERRIDE; // The PcRelativePatchInfo is used for PC-relative addressing of dex cache arrays // and boot image strings. The only difference is the interpretation of the offset_or_index. diff --git a/compiler/optimizing/code_generator_mips64.h b/compiler/optimizing/code_generator_mips64.h index 3910530eb5..2dd409a224 100644 --- a/compiler/optimizing/code_generator_mips64.h +++ b/compiler/optimizing/code_generator_mips64.h @@ -285,10 +285,10 @@ class CodeGeneratorMIPS64 : public CodeGenerator { void SetupBlockedRegisters() const OVERRIDE; - size_t SaveCoreRegister(size_t stack_index, uint32_t reg_id); - size_t RestoreCoreRegister(size_t stack_index, uint32_t reg_id); - size_t SaveFloatingPointRegister(size_t stack_index, uint32_t reg_id); - size_t RestoreFloatingPointRegister(size_t stack_index, uint32_t reg_id); + size_t SaveCoreRegister(size_t stack_index, uint32_t reg_id) OVERRIDE; + size_t RestoreCoreRegister(size_t stack_index, uint32_t reg_id) OVERRIDE; + size_t SaveFloatingPointRegister(size_t stack_index, uint32_t reg_id) OVERRIDE; + size_t RestoreFloatingPointRegister(size_t stack_index, uint32_t reg_id) OVERRIDE; void DumpCoreRegister(std::ostream& stream, int reg) const OVERRIDE; void DumpFloatingPointRegister(std::ostream& stream, int reg) const OVERRIDE; @@ -327,7 +327,7 @@ class CodeGeneratorMIPS64 : public CodeGenerator { ParallelMoveResolver* GetMoveResolver() OVERRIDE { return &move_resolver_; } - bool NeedsTwoRegisters(Primitive::Type type ATTRIBUTE_UNUSED) const { return false; } + bool NeedsTwoRegisters(Primitive::Type type ATTRIBUTE_UNUSED) const OVERRIDE { return false; } // Check if the desired_string_load_kind is supported. If it is, return it, // otherwise return a fall-back kind that should be used instead. @@ -353,9 +353,9 @@ class CodeGeneratorMIPS64 : public CodeGenerator { UNIMPLEMENTED(FATAL) << "Not implemented on MIPS64"; } - void GenerateNop(); - void GenerateImplicitNullCheck(HNullCheck* instruction); - void GenerateExplicitNullCheck(HNullCheck* instruction); + void GenerateNop() OVERRIDE; + void GenerateImplicitNullCheck(HNullCheck* instruction) OVERRIDE; + void GenerateExplicitNullCheck(HNullCheck* instruction) OVERRIDE; private: // Labels for each block that will be compiled. diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h index e2250981bb..04a0a3de6a 100644 --- a/compiler/optimizing/code_generator_x86.h +++ b/compiler/optimizing/code_generator_x86.h @@ -561,9 +561,9 @@ class CodeGeneratorX86 : public CodeGenerator { } } - void GenerateNop(); - void GenerateImplicitNullCheck(HNullCheck* instruction); - void GenerateExplicitNullCheck(HNullCheck* instruction); + void GenerateNop() OVERRIDE; + void GenerateImplicitNullCheck(HNullCheck* instruction) OVERRIDE; + void GenerateExplicitNullCheck(HNullCheck* instruction) OVERRIDE; // When we don't know the proper offset for the value, we use kDummy32BitOffset. // The correct value will be inserted when processing Assembler fixups. diff --git a/compiler/optimizing/code_generator_x86_64.h b/compiler/optimizing/code_generator_x86_64.h index d93908343d..693d0b8d26 100644 --- a/compiler/optimizing/code_generator_x86_64.h +++ b/compiler/optimizing/code_generator_x86_64.h @@ -533,9 +533,9 @@ class CodeGeneratorX86_64 : public CodeGenerator { } } - void GenerateNop(); - void GenerateImplicitNullCheck(HNullCheck* instruction); - void GenerateExplicitNullCheck(HNullCheck* instruction); + void GenerateNop() OVERRIDE; + void GenerateImplicitNullCheck(HNullCheck* instruction) OVERRIDE; + void GenerateExplicitNullCheck(HNullCheck* instruction) OVERRIDE; // When we don't know the proper offset for the value, we use kDummy32BitOffset. // We will fix this up in the linker later to have the right value. diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc index e1bde7c737..aa3f26809a 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -16,7 +16,7 @@ #include "dead_code_elimination.h" -#include "utils/array_ref.h" +#include "base/array_ref.h" #include "base/bit_vector-inl.h" #include "ssa_phi_elimination.h" diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 8f37236ede..9cfa89b7d0 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -460,6 +460,113 @@ GraphAnalysisResult HGraph::AnalyzeLoops() const { return kAnalysisSuccess; } +static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { + return first_loop == second_loop; +} + +static bool IsLoop(HLoopInformation* info) { + return info != nullptr; +} + +static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { + return (inner != outer) + && (inner != nullptr) + && (outer != nullptr) + && inner->IsIn(*outer); +} + +// Helper method to update work list for linear order. +static void AddToListForLinearization(ArenaVector<HBasicBlock*>* worklist, HBasicBlock* block) { + HLoopInformation* block_loop = block->GetLoopInformation(); + auto insert_pos = worklist->rbegin(); // insert_pos.base() will be the actual position. + for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) { + HBasicBlock* current = *insert_pos; + HLoopInformation* current_loop = current->GetLoopInformation(); + if (InSameLoop(block_loop, current_loop) + || !IsLoop(current_loop) + || IsInnerLoop(current_loop, block_loop)) { + // The block can be processed immediately. + break; + } + } + worklist->insert(insert_pos.base(), block); +} + +// Helper method to validate linear order. +static bool IsLinearOrderWellFormed(const HGraph& graph) { + for (HBasicBlock* header : graph.GetBlocks()) { + if (header == nullptr || !header->IsLoopHeader()) { + continue; + } + HLoopInformation* loop = header->GetLoopInformation(); + size_t num_blocks = loop->GetBlocks().NumSetBits(); + size_t found_blocks = 0u; + for (HLinearOrderIterator it(graph); !it.Done(); it.Advance()) { + HBasicBlock* current = it.Current(); + if (loop->Contains(*current)) { + found_blocks++; + if (found_blocks == 1u && current != header) { + // First block is not the header. + return false; + } else if (found_blocks == num_blocks && !loop->IsBackEdge(*current)) { + // Last block is not a back edge. + return false; + } + } else if (found_blocks != 0u && found_blocks != num_blocks) { + // Blocks are not adjacent. + return false; + } + } + DCHECK_EQ(found_blocks, num_blocks); + } + return true; +} + +void HGraph::Linearize() { + // Create a reverse post ordering with the following properties: + // - Blocks in a loop are consecutive, + // - Back-edge is the last block before loop exits. + + // (1): Record the number of forward predecessors for each block. This is to + // ensure the resulting order is reverse post order. We could use the + // current reverse post order in the graph, but it would require making + // order queries to a GrowableArray, which is not the best data structure + // for it. + ArenaVector<uint32_t> forward_predecessors(blocks_.size(), + arena_->Adapter(kArenaAllocSsaLiveness)); + for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + size_t number_of_forward_predecessors = block->GetPredecessors().size(); + if (block->IsLoopHeader()) { + number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges(); + } + forward_predecessors[block->GetBlockId()] = number_of_forward_predecessors; + } + + // (2): Following a worklist approach, first start with the entry block, and + // iterate over the successors. When all non-back edge predecessors of a + // successor block are visited, the successor block is added in the worklist + // following an order that satisfies the requirements to build our linear graph. + linear_order_.reserve(GetReversePostOrder().size()); + ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocSsaLiveness)); + worklist.push_back(GetEntryBlock()); + do { + HBasicBlock* current = worklist.back(); + worklist.pop_back(); + linear_order_.push_back(current); + for (HBasicBlock* successor : current->GetSuccessors()) { + int block_id = successor->GetBlockId(); + size_t number_of_remaining_predecessors = forward_predecessors[block_id]; + if (number_of_remaining_predecessors == 1) { + AddToListForLinearization(&worklist, successor); + } + forward_predecessors[block_id] = number_of_remaining_predecessors - 1; + } + } while (!worklist.empty()); + + DCHECK(HasIrreducibleLoops() || IsLinearOrderWellFormed(*this)); +} + void HLoopInformation::Dump(std::ostream& os) { os << "header: " << header_->GetBlockId() << std::endl; os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl; diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 119b62a16b..7c3ca5cefa 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -24,7 +24,9 @@ #include "base/arena_bit_vector.h" #include "base/arena_containers.h" #include "base/arena_object.h" +#include "base/array_ref.h" #include "base/stl_util.h" +#include "base/transform_array_ref.h" #include "dex_file.h" #include "entrypoints/quick/quick_entrypoints_enum.h" #include "handle.h" @@ -35,9 +37,7 @@ #include "mirror/class.h" #include "offsets.h" #include "primitive.h" -#include "utils/array_ref.h" #include "utils/intrusive_forward_list.h" -#include "utils/transform_array_ref.h" namespace art { @@ -365,6 +365,13 @@ class HGraph : public ArenaObject<kArenaAllocGraph> { // is a throw-catch loop, i.e. the header is a catch block. GraphAnalysisResult AnalyzeLoops() const; + // Computes the linear order (should be called before using HLinearOrderIterator). + // Linearizes the graph such that: + // (1): a block is always after its dominator, + // (2): blocks of loops are contiguous. + // This creates a natural and efficient ordering when visualizing live ranges. + void Linearize(); + // Iterate over blocks to compute try block membership. Needs reverse post // order and loop information. void ComputeTryBlockInformation(); diff --git a/compiler/optimizing/register_allocation_resolver.h b/compiler/optimizing/register_allocation_resolver.h index a70ceae076..d48b1a0bb9 100644 --- a/compiler/optimizing/register_allocation_resolver.h +++ b/compiler/optimizing/register_allocation_resolver.h @@ -18,9 +18,9 @@ #define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATION_RESOLVER_H_ #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/value_object.h" #include "primitive.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index a4d52d7761..9ce34aa80b 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -23,119 +23,11 @@ namespace art { void SsaLivenessAnalysis::Analyze() { - LinearizeGraph(); + graph_->Linearize(); NumberInstructions(); ComputeLiveness(); } -static bool IsLoop(HLoopInformation* info) { - return info != nullptr; -} - -static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { - return first_loop == second_loop; -} - -static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { - return (inner != outer) - && (inner != nullptr) - && (outer != nullptr) - && inner->IsIn(*outer); -} - -static void AddToListForLinearization(ArenaVector<HBasicBlock*>* worklist, HBasicBlock* block) { - HLoopInformation* block_loop = block->GetLoopInformation(); - auto insert_pos = worklist->rbegin(); // insert_pos.base() will be the actual position. - for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) { - HBasicBlock* current = *insert_pos; - HLoopInformation* current_loop = current->GetLoopInformation(); - if (InSameLoop(block_loop, current_loop) - || !IsLoop(current_loop) - || IsInnerLoop(current_loop, block_loop)) { - // The block can be processed immediately. - break; - } - } - worklist->insert(insert_pos.base(), block); -} - -static bool IsLinearOrderWellFormed(const HGraph& graph) { - for (HBasicBlock* header : graph.GetBlocks()) { - if (header == nullptr || !header->IsLoopHeader()) { - continue; - } - - HLoopInformation* loop = header->GetLoopInformation(); - size_t num_blocks = loop->GetBlocks().NumSetBits(); - size_t found_blocks = 0u; - - for (HLinearOrderIterator it(graph); !it.Done(); it.Advance()) { - HBasicBlock* current = it.Current(); - if (loop->Contains(*current)) { - found_blocks++; - if (found_blocks == 1u && current != header) { - // First block is not the header. - return false; - } else if (found_blocks == num_blocks && !loop->IsBackEdge(*current)) { - // Last block is not a back edge. - return false; - } - } else if (found_blocks != 0u && found_blocks != num_blocks) { - // Blocks are not adjacent. - return false; - } - } - DCHECK_EQ(found_blocks, num_blocks); - } - - return true; -} - -void SsaLivenessAnalysis::LinearizeGraph() { - // Create a reverse post ordering with the following properties: - // - Blocks in a loop are consecutive, - // - Back-edge is the last block before loop exits. - - // (1): Record the number of forward predecessors for each block. This is to - // ensure the resulting order is reverse post order. We could use the - // current reverse post order in the graph, but it would require making - // order queries to a GrowableArray, which is not the best data structure - // for it. - ArenaVector<uint32_t> forward_predecessors(graph_->GetBlocks().size(), - graph_->GetArena()->Adapter(kArenaAllocSsaLiveness)); - for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { - HBasicBlock* block = it.Current(); - size_t number_of_forward_predecessors = block->GetPredecessors().size(); - if (block->IsLoopHeader()) { - number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges(); - } - forward_predecessors[block->GetBlockId()] = number_of_forward_predecessors; - } - - // (2): Following a worklist approach, first start with the entry block, and - // iterate over the successors. When all non-back edge predecessors of a - // successor block are visited, the successor block is added in the worklist - // following an order that satisfies the requirements to build our linear graph. - graph_->linear_order_.reserve(graph_->GetReversePostOrder().size()); - ArenaVector<HBasicBlock*> worklist(graph_->GetArena()->Adapter(kArenaAllocSsaLiveness)); - worklist.push_back(graph_->GetEntryBlock()); - do { - HBasicBlock* current = worklist.back(); - worklist.pop_back(); - graph_->linear_order_.push_back(current); - for (HBasicBlock* successor : current->GetSuccessors()) { - int block_id = successor->GetBlockId(); - size_t number_of_remaining_predecessors = forward_predecessors[block_id]; - if (number_of_remaining_predecessors == 1) { - AddToListForLinearization(&worklist, successor); - } - forward_predecessors[block_id] = number_of_remaining_predecessors - 1; - } - } while (!worklist.empty()); - - DCHECK(graph_->HasIrreducibleLoops() || IsLinearOrderWellFormed(*graph_)); -} - void SsaLivenessAnalysis::NumberInstructions() { int ssa_index = 0; size_t lifetime_position = 0; diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index 0be16118b1..b62bf4e5f9 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -1186,12 +1186,6 @@ class SsaLivenessAnalysis : public ValueObject { static constexpr const char* kLivenessPassName = "liveness"; private: - // Linearize the graph so that: - // (1): a block is always after its dominator, - // (2): blocks of loops are contiguous. - // This creates a natural and efficient ordering when visualizing live ranges. - void LinearizeGraph(); - // Give an SSA number to each instruction that defines a value used by another instruction, // and setup the lifetime information of each instruction and block. void NumberInstructions(); diff --git a/compiler/utils/arm/assembler_thumb2.h b/compiler/utils/arm/assembler_thumb2.h index 13f3becb6d..353555d0e8 100644 --- a/compiler/utils/arm/assembler_thumb2.h +++ b/compiler/utils/arm/assembler_thumb2.h @@ -22,11 +22,11 @@ #include <vector> #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/logging.h" #include "constants_arm.h" #include "utils/arm/managed_register_arm.h" #include "utils/arm/assembler_arm.h" -#include "utils/array_ref.h" #include "offsets.h" namespace art { diff --git a/compiler/utils/arm/jni_macro_assembler_arm_vixl.cc b/compiler/utils/arm/jni_macro_assembler_arm_vixl.cc index a03dd74657..14d29c4f1a 100644 --- a/compiler/utils/arm/jni_macro_assembler_arm_vixl.cc +++ b/compiler/utils/arm/jni_macro_assembler_arm_vixl.cc @@ -314,11 +314,21 @@ void ArmVIXLJNIMacroAssembler::Move(ManagedRegister m_dst, CHECK(src.IsCoreRegister()) << src; ___ Mov(dst.AsVIXLRegister(), src.AsVIXLRegister()); } else if (dst.IsDRegister()) { - CHECK(src.IsDRegister()) << src; - ___ Vmov(F64, dst.AsVIXLDRegister(), src.AsVIXLDRegister()); + if (src.IsDRegister()) { + ___ Vmov(F64, dst.AsVIXLDRegister(), src.AsVIXLDRegister()); + } else { + // VMOV Dn, Rlo, Rhi (Dn = {Rlo, Rhi}) + CHECK(src.IsRegisterPair()) << src; + ___ Vmov(dst.AsVIXLDRegister(), src.AsVIXLRegisterPairLow(), src.AsVIXLRegisterPairHigh()); + } } else if (dst.IsSRegister()) { - CHECK(src.IsSRegister()) << src; - ___ Vmov(F32, dst.AsVIXLSRegister(), src.AsVIXLSRegister()); + if (src.IsSRegister()) { + ___ Vmov(F32, dst.AsVIXLSRegister(), src.AsVIXLSRegister()); + } else { + // VMOV Sn, Rn (Sn = Rn) + CHECK(src.IsCoreRegister()) << src; + ___ Vmov(dst.AsVIXLSRegister(), src.AsVIXLRegister()); + } } else { CHECK(dst.IsRegisterPair()) << dst; CHECK(src.IsRegisterPair()) << src; diff --git a/compiler/utils/assembler.h b/compiler/utils/assembler.h index b616057e79..314ff8cf7a 100644 --- a/compiler/utils/assembler.h +++ b/compiler/utils/assembler.h @@ -24,6 +24,7 @@ #include "arm/constants_arm.h" #include "base/arena_allocator.h" #include "base/arena_object.h" +#include "base/array_ref.h" #include "base/enums.h" #include "base/logging.h" #include "base/macros.h" @@ -33,7 +34,6 @@ #include "memory_region.h" #include "mips/constants_mips.h" #include "offsets.h" -#include "utils/array_ref.h" #include "x86/constants_x86.h" #include "x86_64/constants_x86_64.h" diff --git a/compiler/utils/dedupe_set_test.cc b/compiler/utils/dedupe_set_test.cc index 60a891d6a2..4c0979e0b7 100644 --- a/compiler/utils/dedupe_set_test.cc +++ b/compiler/utils/dedupe_set_test.cc @@ -20,10 +20,10 @@ #include <cstdio> #include <vector> +#include "base/array_ref.h" #include "dedupe_set-inl.h" #include "gtest/gtest.h" #include "thread-inl.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/utils/jni_macro_assembler.h b/compiler/utils/jni_macro_assembler.h index 6f45bd62db..0119ae9bfb 100644 --- a/compiler/utils/jni_macro_assembler.h +++ b/compiler/utils/jni_macro_assembler.h @@ -22,12 +22,12 @@ #include "arch/instruction_set.h" #include "base/arena_allocator.h" #include "base/arena_object.h" +#include "base/array_ref.h" #include "base/enums.h" #include "base/logging.h" #include "base/macros.h" #include "managed_register.h" #include "offsets.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/utils/x86/assembler_x86.h b/compiler/utils/x86/assembler_x86.h index 9738784d45..114986b3e7 100644 --- a/compiler/utils/x86/assembler_x86.h +++ b/compiler/utils/x86/assembler_x86.h @@ -20,6 +20,7 @@ #include <vector> #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/bit_utils.h" #include "base/enums.h" #include "base/macros.h" @@ -27,7 +28,6 @@ #include "globals.h" #include "managed_register_x86.h" #include "offsets.h" -#include "utils/array_ref.h" #include "utils/assembler.h" namespace art { diff --git a/compiler/utils/x86/jni_macro_assembler_x86.h b/compiler/utils/x86/jni_macro_assembler_x86.h index 3f07ede865..015584cbc1 100644 --- a/compiler/utils/x86/jni_macro_assembler_x86.h +++ b/compiler/utils/x86/jni_macro_assembler_x86.h @@ -21,10 +21,10 @@ #include "assembler_x86.h" #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/enums.h" #include "base/macros.h" #include "offsets.h" -#include "utils/array_ref.h" #include "utils/jni_macro_assembler.h" namespace art { diff --git a/compiler/utils/x86_64/assembler_x86_64.h b/compiler/utils/x86_64/assembler_x86_64.h index fdd3aa9317..acad86d161 100644 --- a/compiler/utils/x86_64/assembler_x86_64.h +++ b/compiler/utils/x86_64/assembler_x86_64.h @@ -20,13 +20,13 @@ #include <vector> #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/bit_utils.h" #include "base/macros.h" #include "constants_x86_64.h" #include "globals.h" #include "managed_register_x86_64.h" #include "offsets.h" -#include "utils/array_ref.h" #include "utils/assembler.h" #include "utils/jni_macro_assembler.h" diff --git a/compiler/utils/x86_64/jni_macro_assembler_x86_64.h b/compiler/utils/x86_64/jni_macro_assembler_x86_64.h index cc4e57c999..9107f3c422 100644 --- a/compiler/utils/x86_64/jni_macro_assembler_x86_64.h +++ b/compiler/utils/x86_64/jni_macro_assembler_x86_64.h @@ -21,10 +21,10 @@ #include "assembler_x86_64.h" #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/enums.h" #include "base/macros.h" #include "offsets.h" -#include "utils/array_ref.h" #include "utils/assembler.h" #include "utils/jni_macro_assembler.h" diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc index 1dd91321c5..1296bcf525 100644 --- a/dex2oat/dex2oat.cc +++ b/dex2oat/dex2oat.cc @@ -2782,6 +2782,8 @@ static int dex2oat(int argc, char** argv) { return EXIT_FAILURE; } + VLOG(compiler) << "Running dex2oat (parent PID = " << getppid() << ")"; + bool result; if (dex2oat->IsImage()) { result = CompileImage(*dex2oat); diff --git a/dexlist/dexlist_test.cc b/dexlist/dexlist_test.cc index 9a65ba647c..da1dd7fd89 100644 --- a/dexlist/dexlist_test.cc +++ b/dexlist/dexlist_test.cc @@ -43,11 +43,7 @@ class DexListTest : public CommonRuntimeTest { // Runs test with given arguments. bool Exec(const std::vector<std::string>& args, std::string* error_msg) { std::string file_path = GetTestAndroidRoot(); - if (IsHost()) { - file_path += "/bin/dexlist"; - } else { - file_path += "/xbin/dexlist"; - } + file_path += "/bin/dexlist"; EXPECT_TRUE(OS::FileExists(file_path.c_str())) << file_path << " should be a valid file path"; std::vector<std::string> exec_argv = { file_path }; exec_argv.insert(exec_argv.end(), args.begin(), args.end()); diff --git a/compiler/utils/array_ref.h b/runtime/base/array_ref.h index 8dc9ab4a5e..00b9bad6bf 100644 --- a/compiler/utils/array_ref.h +++ b/runtime/base/array_ref.h @@ -14,8 +14,8 @@ * limitations under the License. */ -#ifndef ART_COMPILER_UTILS_ARRAY_REF_H_ -#define ART_COMPILER_UTILS_ARRAY_REF_H_ +#ifndef ART_RUNTIME_BASE_ARRAY_REF_H_ +#define ART_RUNTIME_BASE_ARRAY_REF_H_ #include <type_traits> #include <vector> @@ -197,4 +197,4 @@ bool operator!=(const ArrayRef<T>& lhs, const ArrayRef<T>& rhs) { } // namespace art -#endif // ART_COMPILER_UTILS_ARRAY_REF_H_ +#endif // ART_RUNTIME_BASE_ARRAY_REF_H_ diff --git a/compiler/utils/transform_array_ref.h b/runtime/base/transform_array_ref.h index a6da34fb40..a4e0bc27ed 100644 --- a/compiler/utils/transform_array_ref.h +++ b/runtime/base/transform_array_ref.h @@ -14,13 +14,13 @@ * limitations under the License. */ -#ifndef ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_ -#define ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_ +#ifndef ART_RUNTIME_BASE_TRANSFORM_ARRAY_REF_H_ +#define ART_RUNTIME_BASE_TRANSFORM_ARRAY_REF_H_ #include <type_traits> -#include "utils/array_ref.h" -#include "utils/transform_iterator.h" +#include "base/array_ref.h" +#include "base/transform_iterator.h" namespace art { @@ -193,4 +193,4 @@ TransformArrayRef<const typename Container::value_type, Function> MakeTransformA } // namespace art -#endif // ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_ +#endif // ART_RUNTIME_BASE_TRANSFORM_ARRAY_REF_H_ diff --git a/compiler/utils/transform_array_ref_test.cc b/runtime/base/transform_array_ref_test.cc index 8d71fd7179..494dbb29aa 100644 --- a/compiler/utils/transform_array_ref_test.cc +++ b/runtime/base/transform_array_ref_test.cc @@ -19,7 +19,7 @@ #include "gtest/gtest.h" -#include "utils/transform_array_ref.h" +#include "base/transform_array_ref.h" namespace art { diff --git a/compiler/utils/transform_iterator.h b/runtime/base/transform_iterator.h index 3bc9046408..9c8f822b71 100644 --- a/compiler/utils/transform_iterator.h +++ b/runtime/base/transform_iterator.h @@ -14,8 +14,8 @@ * limitations under the License. */ -#ifndef ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_ -#define ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_ +#ifndef ART_RUNTIME_BASE_TRANSFORM_ITERATOR_H_ +#define ART_RUNTIME_BASE_TRANSFORM_ITERATOR_H_ #include <iterator> #include <type_traits> @@ -175,4 +175,4 @@ auto MakeTransformRange(BaseRange& range, Function f) { } // namespace art -#endif // ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_ +#endif // ART_RUNTIME_BASE_TRANSFORM_ITERATOR_H_ diff --git a/compiler/utils/transform_iterator_test.cc b/runtime/base/transform_iterator_test.cc index 57ff0a62ac..a85dda8958 100644 --- a/compiler/utils/transform_iterator_test.cc +++ b/runtime/base/transform_iterator_test.cc @@ -22,7 +22,7 @@ #include "gtest/gtest.h" -#include "utils/transform_iterator.h" +#include "base/transform_iterator.h" namespace art { |