Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2018 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #ifndef ART_COMPILER_OPTIMIZING_LOOP_ANALYSIS_H_ |
| 18 | #define ART_COMPILER_OPTIMIZING_LOOP_ANALYSIS_H_ |
| 19 | |
| 20 | #include "nodes.h" |
| 21 | |
| 22 | namespace art { |
| 23 | |
| 24 | class LoopAnalysis; |
| 25 | |
| 26 | // No loop unrolling factor (just one copy of the loop-body). |
| 27 | static constexpr uint32_t kNoUnrollingFactor = 1; |
| 28 | |
| 29 | // Class to hold cached information on properties of the loop. |
| 30 | class LoopAnalysisInfo : public ValueObject { |
| 31 | public: |
| 32 | explicit LoopAnalysisInfo(HLoopInformation* loop_info) |
| 33 | : bb_num_(0), |
| 34 | instr_num_(0), |
| 35 | exits_num_(0), |
Artem Serov | 72411e6 | 2017-10-19 16:18:07 +0100 | [diff] [blame] | 36 | has_instructions_preventing_scalar_peeling_(false), |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 37 | has_instructions_preventing_scalar_unrolling_(false), |
Artem Serov | cf43fb6 | 2018-02-15 14:43:48 +0000 | [diff] [blame] | 38 | has_long_type_instructions_(false), |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 39 | loop_info_(loop_info) {} |
| 40 | |
| 41 | size_t GetNumberOfBasicBlocks() const { return bb_num_; } |
| 42 | size_t GetNumberOfInstructions() const { return instr_num_; } |
| 43 | size_t GetNumberOfExits() const { return exits_num_; } |
| 44 | |
Artem Serov | 72411e6 | 2017-10-19 16:18:07 +0100 | [diff] [blame] | 45 | bool HasInstructionsPreventingScalarPeeling() const { |
| 46 | return has_instructions_preventing_scalar_peeling_; |
| 47 | } |
| 48 | |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 49 | bool HasInstructionsPreventingScalarUnrolling() const { |
| 50 | return has_instructions_preventing_scalar_unrolling_; |
| 51 | } |
| 52 | |
Artem Serov | cf43fb6 | 2018-02-15 14:43:48 +0000 | [diff] [blame] | 53 | bool HasLongTypeInstructions() const { |
| 54 | return has_long_type_instructions_; |
| 55 | } |
| 56 | |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 57 | const HLoopInformation* GetLoopInfo() const { return loop_info_; } |
| 58 | |
| 59 | private: |
| 60 | // Number of basic blocks in the loop body. |
| 61 | size_t bb_num_; |
| 62 | // Number of instructions in the loop body. |
| 63 | size_t instr_num_; |
| 64 | // Number of loop's exits. |
| 65 | size_t exits_num_; |
Artem Serov | 72411e6 | 2017-10-19 16:18:07 +0100 | [diff] [blame] | 66 | // Whether the loop has instructions which make scalar loop peeling non-beneficial. |
| 67 | bool has_instructions_preventing_scalar_peeling_; |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 68 | // Whether the loop has instructions which make scalar loop unrolling non-beneficial. |
| 69 | bool has_instructions_preventing_scalar_unrolling_; |
Artem Serov | cf43fb6 | 2018-02-15 14:43:48 +0000 | [diff] [blame] | 70 | // Whether the loop has instructions of primitive long type; unrolling these loop will |
| 71 | // likely introduce spill/fills on 32-bit targets. |
| 72 | bool has_long_type_instructions_; |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 73 | |
| 74 | // Corresponding HLoopInformation. |
| 75 | const HLoopInformation* loop_info_; |
| 76 | |
| 77 | friend class LoopAnalysis; |
| 78 | }; |
| 79 | |
| 80 | // Placeholder class for methods and routines used to analyse loops, calculate loop properties |
| 81 | // and characteristics. |
| 82 | class LoopAnalysis : public ValueObject { |
| 83 | public: |
| 84 | // Calculates loops basic properties like body size, exits number, etc. and fills |
| 85 | // 'analysis_results' with this information. |
| 86 | static void CalculateLoopBasicProperties(HLoopInformation* loop_info, |
| 87 | LoopAnalysisInfo* analysis_results); |
| 88 | |
Artem Serov | 72411e6 | 2017-10-19 16:18:07 +0100 | [diff] [blame] | 89 | // Returns whether the loop has at least one loop invariant exit. |
| 90 | static bool HasLoopAtLeastOneInvariantExit(HLoopInformation* loop_info); |
| 91 | |
| 92 | // Returns whether HIf's true or false successor is outside the specified loop. |
| 93 | // |
| 94 | // Prerequisite: HIf must be in the specified loop. |
| 95 | static bool IsLoopExit(HLoopInformation* loop_info, const HIf* hif) { |
| 96 | DCHECK(loop_info->Contains(*hif->GetBlock())); |
| 97 | HBasicBlock* true_succ = hif->IfTrueSuccessor(); |
| 98 | HBasicBlock* false_succ = hif->IfFalseSuccessor(); |
| 99 | return (!loop_info->Contains(*true_succ) || !loop_info->Contains(*false_succ)); |
| 100 | } |
| 101 | |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 102 | private: |
Artem Serov | 72411e6 | 2017-10-19 16:18:07 +0100 | [diff] [blame] | 103 | // Returns whether an instruction makes scalar loop peeling/unrolling non-beneficial. |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 104 | // |
| 105 | // If in the loop body we have a dex/runtime call then its contribution to the whole |
Artem Serov | 72411e6 | 2017-10-19 16:18:07 +0100 | [diff] [blame] | 106 | // loop performance will probably prevail. So peeling/unrolling optimization will not bring |
| 107 | // any noticeable performance improvement. It will increase the code size. |
| 108 | static bool MakesScalarPeelingUnrollingNonBeneficial(HInstruction* instruction) { |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 109 | return (instruction->IsNewArray() || |
| 110 | instruction->IsNewInstance() || |
| 111 | instruction->IsUnresolvedInstanceFieldGet() || |
| 112 | instruction->IsUnresolvedInstanceFieldSet() || |
| 113 | instruction->IsUnresolvedStaticFieldGet() || |
| 114 | instruction->IsUnresolvedStaticFieldSet() || |
Artem Serov | 72411e6 | 2017-10-19 16:18:07 +0100 | [diff] [blame] | 115 | // TODO: Support loops with intrinsified invokes. |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 116 | instruction->IsInvoke() || |
Artem Serov | 72411e6 | 2017-10-19 16:18:07 +0100 | [diff] [blame] | 117 | // TODO: Support loops with ClinitChecks. |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 118 | instruction->IsClinitCheck()); |
| 119 | } |
| 120 | }; |
| 121 | |
| 122 | // |
| 123 | // Helper class which holds target-dependent methods and constants needed for loop optimizations. |
| 124 | // |
| 125 | // To support peeling/unrolling for a new architecture one needs to create new helper class, |
| 126 | // inherit it from this and add implementation for the following methods. |
| 127 | // |
Artem Serov | cf43fb6 | 2018-02-15 14:43:48 +0000 | [diff] [blame] | 128 | class ArchNoOptsLoopHelper : public ArenaObject<kArenaAllocOptimization> { |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 129 | public: |
Artem Serov | cf43fb6 | 2018-02-15 14:43:48 +0000 | [diff] [blame] | 130 | virtual ~ArchNoOptsLoopHelper() {} |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 131 | |
| 132 | // Creates an instance of specialised helper for the target or default helper if the target |
| 133 | // doesn't support loop peeling and unrolling. |
Artem Serov | cf43fb6 | 2018-02-15 14:43:48 +0000 | [diff] [blame] | 134 | static ArchNoOptsLoopHelper* Create(InstructionSet isa, ArenaAllocator* allocator); |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 135 | |
Artem Serov | cf43fb6 | 2018-02-15 14:43:48 +0000 | [diff] [blame] | 136 | // Returns whether the loop is not beneficial for loop peeling/unrolling. |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 137 | // |
Artem Serov | cf43fb6 | 2018-02-15 14:43:48 +0000 | [diff] [blame] | 138 | // For example, if the loop body has too many instructions then peeling/unrolling optimization |
| 139 | // will not bring any noticeable performance improvement however will increase the code size. |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 140 | // |
| 141 | // Returns 'true' by default, should be overridden by particular target loop helper. |
Artem Serov | cf43fb6 | 2018-02-15 14:43:48 +0000 | [diff] [blame] | 142 | virtual bool IsLoopNonBeneficialForScalarOpts( |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 143 | LoopAnalysisInfo* loop_analysis_info ATTRIBUTE_UNUSED) const { return true; } |
| 144 | |
| 145 | // Returns optimal scalar unrolling factor for the loop. |
| 146 | // |
| 147 | // Returns kNoUnrollingFactor by default, should be overridden by particular target loop helper. |
| 148 | virtual uint32_t GetScalarUnrollingFactor(HLoopInformation* loop_info ATTRIBUTE_UNUSED, |
| 149 | uint64_t trip_count ATTRIBUTE_UNUSED) const { |
| 150 | return kNoUnrollingFactor; |
| 151 | } |
| 152 | |
Artem Serov | 72411e6 | 2017-10-19 16:18:07 +0100 | [diff] [blame] | 153 | // Returns whether scalar loop peeling is enabled, |
| 154 | // |
| 155 | // Returns 'false' by default, should be overridden by particular target loop helper. |
| 156 | virtual bool IsLoopPeelingEnabled() const { return false; } |
| 157 | |
Artem Serov | 121f203 | 2017-10-23 19:19:06 +0100 | [diff] [blame] | 158 | // Returns optimal SIMD unrolling factor for the loop. |
| 159 | // |
| 160 | // Returns kNoUnrollingFactor by default, should be overridden by particular target loop helper. |
| 161 | virtual uint32_t GetSIMDUnrollingFactor(HBasicBlock* block ATTRIBUTE_UNUSED, |
| 162 | int64_t trip_count ATTRIBUTE_UNUSED, |
| 163 | uint32_t max_peel ATTRIBUTE_UNUSED, |
| 164 | uint32_t vector_length ATTRIBUTE_UNUSED) const { |
| 165 | return kNoUnrollingFactor; |
| 166 | } |
| 167 | }; |
| 168 | |
| 169 | } // namespace art |
| 170 | |
| 171 | #endif // ART_COMPILER_OPTIMIZING_LOOP_ANALYSIS_H_ |