ART: Implement scalar loop unrolling.
Implement scalar loop unrolling for small loops
(on arm64) with known trip count to reduce loop check
and branch penalty and to provide more opportunities
for instruction scheduling.
Note: this functionality is turned off by default now.
Test: cloner_test.cc
Test: test-art-target, test-art-host
Change-Id: Ic27fd8fb0bc0d7b69251252da37b8b510bc30acc
diff --git a/compiler/optimizing/loop_analysis.h b/compiler/optimizing/loop_analysis.h
new file mode 100644
index 0000000..bad406f
--- /dev/null
+++ b/compiler/optimizing/loop_analysis.h
@@ -0,0 +1,139 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_LOOP_ANALYSIS_H_
+#define ART_COMPILER_OPTIMIZING_LOOP_ANALYSIS_H_
+
+#include "nodes.h"
+
+namespace art {
+
+class LoopAnalysis;
+
+// No loop unrolling factor (just one copy of the loop-body).
+static constexpr uint32_t kNoUnrollingFactor = 1;
+
+// Class to hold cached information on properties of the loop.
+class LoopAnalysisInfo : public ValueObject {
+ public:
+ explicit LoopAnalysisInfo(HLoopInformation* loop_info)
+ : bb_num_(0),
+ instr_num_(0),
+ exits_num_(0),
+ has_instructions_preventing_scalar_unrolling_(false),
+ loop_info_(loop_info) {}
+
+ size_t GetNumberOfBasicBlocks() const { return bb_num_; }
+ size_t GetNumberOfInstructions() const { return instr_num_; }
+ size_t GetNumberOfExits() const { return exits_num_; }
+
+ bool HasInstructionsPreventingScalarUnrolling() const {
+ return has_instructions_preventing_scalar_unrolling_;
+ }
+
+ const HLoopInformation* GetLoopInfo() const { return loop_info_; }
+
+ private:
+ // Number of basic blocks in the loop body.
+ size_t bb_num_;
+ // Number of instructions in the loop body.
+ size_t instr_num_;
+ // Number of loop's exits.
+ size_t exits_num_;
+ // Whether the loop has instructions which make scalar loop unrolling non-beneficial.
+ bool has_instructions_preventing_scalar_unrolling_;
+
+ // Corresponding HLoopInformation.
+ const HLoopInformation* loop_info_;
+
+ friend class LoopAnalysis;
+};
+
+// Placeholder class for methods and routines used to analyse loops, calculate loop properties
+// and characteristics.
+class LoopAnalysis : public ValueObject {
+ public:
+ // Calculates loops basic properties like body size, exits number, etc. and fills
+ // 'analysis_results' with this information.
+ static void CalculateLoopBasicProperties(HLoopInformation* loop_info,
+ LoopAnalysisInfo* analysis_results);
+
+ private:
+ // Returns whether an instruction makes scalar loop unrolling non-beneficial.
+ //
+ // If in the loop body we have a dex/runtime call then its contribution to the whole
+ // loop performance will probably prevail. So unrolling optimization will not bring
+ // any noticeable performance improvement however will increase the code size.
+ static bool MakesScalarUnrollingNonBeneficial(HInstruction* instruction) {
+ return (instruction->IsNewArray() ||
+ instruction->IsNewInstance() ||
+ instruction->IsUnresolvedInstanceFieldGet() ||
+ instruction->IsUnresolvedInstanceFieldSet() ||
+ instruction->IsUnresolvedStaticFieldGet() ||
+ instruction->IsUnresolvedStaticFieldSet() ||
+ // TODO: Unroll loops with intrinsified invokes.
+ instruction->IsInvoke() ||
+ // TODO: Unroll loops with ClinitChecks.
+ instruction->IsClinitCheck());
+ }
+};
+
+//
+// Helper class which holds target-dependent methods and constants needed for loop optimizations.
+//
+// To support peeling/unrolling for a new architecture one needs to create new helper class,
+// inherit it from this and add implementation for the following methods.
+//
+class ArchDefaultLoopHelper : public ArenaObject<kArenaAllocOptimization> {
+ public:
+ virtual ~ArchDefaultLoopHelper() {}
+
+ // Creates an instance of specialised helper for the target or default helper if the target
+ // doesn't support loop peeling and unrolling.
+ static ArchDefaultLoopHelper* Create(InstructionSet isa, ArenaAllocator* allocator);
+
+ // Returns whether the loop is too big for loop unrolling by checking its total number of
+ // basic blocks and instructions.
+ //
+ // If the loop body has too many instructions then unrolling optimization will not bring
+ // any noticeable performance improvement however will increase the code size.
+ //
+ // Returns 'true' by default, should be overridden by particular target loop helper.
+ virtual bool IsLoopTooBigForScalarUnrolling(
+ LoopAnalysisInfo* loop_analysis_info ATTRIBUTE_UNUSED) const { return true; }
+
+ // Returns optimal scalar unrolling factor for the loop.
+ //
+ // Returns kNoUnrollingFactor by default, should be overridden by particular target loop helper.
+ virtual uint32_t GetScalarUnrollingFactor(HLoopInformation* loop_info ATTRIBUTE_UNUSED,
+ uint64_t trip_count ATTRIBUTE_UNUSED) const {
+ return kNoUnrollingFactor;
+ }
+
+ // Returns optimal SIMD unrolling factor for the loop.
+ //
+ // Returns kNoUnrollingFactor by default, should be overridden by particular target loop helper.
+ virtual uint32_t GetSIMDUnrollingFactor(HBasicBlock* block ATTRIBUTE_UNUSED,
+ int64_t trip_count ATTRIBUTE_UNUSED,
+ uint32_t max_peel ATTRIBUTE_UNUSED,
+ uint32_t vector_length ATTRIBUTE_UNUSED) const {
+ return kNoUnrollingFactor;
+ }
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_LOOP_ANALYSIS_H_