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 InductionVarRange; 25 class LoopAnalysis; 26 27 // Class to hold cached information on properties of the loop. 28 class LoopAnalysisInfo : public ValueObject { 29 public: 30 // No loop unrolling factor (just one copy of the loop-body). 31 static constexpr uint32_t kNoUnrollingFactor = 1; 32 // Used for unknown and non-constant trip counts (see InductionVarRange::HasKnownTripCount). 33 static constexpr int64_t kUnknownTripCount = -1; 34 35 explicit LoopAnalysisInfo(HLoopInformation* loop_info) 36 : trip_count_(kUnknownTripCount), 37 bb_num_(0), 38 instr_num_(0), 39 exits_num_(0), 40 invariant_exits_num_(0), 41 has_instructions_preventing_scalar_peeling_(false), 42 has_instructions_preventing_scalar_unrolling_(false), 43 has_long_type_instructions_(false), 44 loop_info_(loop_info) {} 45 46 int64_t GetTripCount() const { return trip_count_; } 47 size_t GetNumberOfBasicBlocks() const { return bb_num_; } 48 size_t GetNumberOfInstructions() const { return instr_num_; } 49 size_t GetNumberOfExits() const { return exits_num_; } 50 size_t GetNumberOfInvariantExits() const { return invariant_exits_num_; } 51 52 bool HasInstructionsPreventingScalarPeeling() const { 53 return has_instructions_preventing_scalar_peeling_; 54 } 55 56 bool HasInstructionsPreventingScalarUnrolling() const { 57 return has_instructions_preventing_scalar_unrolling_; 58 } 59 60 bool HasInstructionsPreventingScalarOpts() const { 61 return HasInstructionsPreventingScalarPeeling() || HasInstructionsPreventingScalarUnrolling(); 62 } 63 64 bool HasLongTypeInstructions() const { 65 return has_long_type_instructions_; 66 } 67 68 HLoopInformation* GetLoopInfo() const { return loop_info_; } 69 70 private: 71 // Trip count of the loop if known, kUnknownTripCount otherwise. 72 int64_t trip_count_; 73 // Number of basic blocks in the loop body. 74 size_t bb_num_; 75 // Number of instructions in the loop body. 76 size_t instr_num_; 77 // Number of loop's exits. 78 size_t exits_num_; 79 // Number of "if" loop exits (with HIf instruction) whose condition is loop-invariant. 80 size_t invariant_exits_num_; 81 // Whether the loop has instructions which make scalar loop peeling non-beneficial. 82 bool has_instructions_preventing_scalar_peeling_; 83 // Whether the loop has instructions which make scalar loop unrolling non-beneficial. 84 bool has_instructions_preventing_scalar_unrolling_; 85 // Whether the loop has instructions of primitive long type; unrolling these loop will 86 // likely introduce spill/fills on 32-bit targets. 87 bool has_long_type_instructions_; 88 89 // Corresponding HLoopInformation. 90 HLoopInformation* loop_info_; 91 92 friend class LoopAnalysis; 93 }; 94 95 // Placeholder class for methods and routines used to analyse loops, calculate loop properties 96 // and characteristics. 97 class LoopAnalysis : public ValueObject { 98 public: 99 // Calculates loops basic properties like body size, exits number, etc. and fills 100 // 'analysis_results' with this information. 101 static void CalculateLoopBasicProperties(HLoopInformation* loop_info, 102 LoopAnalysisInfo* analysis_results, 103 int64_t trip_count); 104 105 // Returns the trip count of the loop if it is known and kUnknownTripCount otherwise. 106 static int64_t GetLoopTripCount(HLoopInformation* loop_info, 107 const InductionVarRange* induction_range); 108 109 private: 110 // Returns whether an instruction makes scalar loop peeling/unrolling non-beneficial. 111 // 112 // If in the loop body we have a dex/runtime call then its contribution to the whole 113 // loop performance will probably prevail. So peeling/unrolling optimization will not bring 114 // any noticeable performance improvement. It will increase the code size. 115 static bool MakesScalarPeelingUnrollingNonBeneficial(HInstruction* instruction) { 116 return (instruction->IsNewArray() || 117 instruction->IsNewInstance() || 118 instruction->IsUnresolvedInstanceFieldGet() || 119 instruction->IsUnresolvedInstanceFieldSet() || 120 instruction->IsUnresolvedStaticFieldGet() || 121 instruction->IsUnresolvedStaticFieldSet() || 122 // TODO: Support loops with intrinsified invokes. 123 instruction->IsInvoke()); 124 } 125 }; 126 127 // 128 // Helper class which holds target-dependent methods and constants needed for loop optimizations. 129 // 130 // To support peeling/unrolling for a new architecture one needs to create new helper class, 131 // inherit it from this and add implementation for the following methods. 132 // 133 class ArchNoOptsLoopHelper : public ArenaObject<kArenaAllocOptimization> { 134 public: 135 virtual ~ArchNoOptsLoopHelper() {} 136 137 // Creates an instance of specialised helper for the target or default helper if the target 138 // doesn't support loop peeling and unrolling. 139 static ArchNoOptsLoopHelper* Create(InstructionSet isa, ArenaAllocator* allocator); 140 141 // Returns whether the loop is not beneficial for loop peeling/unrolling. 142 // 143 // For example, if the loop body has too many instructions then peeling/unrolling optimization 144 // will not bring any noticeable performance improvement however will increase the code size. 145 // 146 // Returns 'true' by default, should be overridden by particular target loop helper. 147 virtual bool IsLoopNonBeneficialForScalarOpts( 148 LoopAnalysisInfo* loop_analysis_info ATTRIBUTE_UNUSED) const { return true; } 149 150 // Returns optimal scalar unrolling factor for the loop. 151 // 152 // Returns kNoUnrollingFactor by default, should be overridden by particular target loop helper. 153 virtual uint32_t GetScalarUnrollingFactor( 154 const LoopAnalysisInfo* analysis_info ATTRIBUTE_UNUSED) const { 155 return LoopAnalysisInfo::kNoUnrollingFactor; 156 } 157 158 // Returns whether scalar loop peeling is enabled, 159 // 160 // Returns 'false' by default, should be overridden by particular target loop helper. 161 virtual bool IsLoopPeelingEnabled() const { return false; } 162 163 // Returns whether it is beneficial to fully unroll the loop. 164 // 165 // Returns 'false' by default, should be overridden by particular target loop helper. 166 virtual bool IsFullUnrollingBeneficial(LoopAnalysisInfo* analysis_info ATTRIBUTE_UNUSED) const { 167 return false; 168 } 169 170 // Returns optimal SIMD unrolling factor for the loop. 171 // 172 // Returns kNoUnrollingFactor by default, should be overridden by particular target loop helper. 173 virtual uint32_t GetSIMDUnrollingFactor(HBasicBlock* block ATTRIBUTE_UNUSED, 174 int64_t trip_count ATTRIBUTE_UNUSED, 175 uint32_t max_peel ATTRIBUTE_UNUSED, 176 uint32_t vector_length ATTRIBUTE_UNUSED) const { 177 return LoopAnalysisInfo::kNoUnrollingFactor; 178 } 179 }; 180 181 } // namespace art 182 183 #endif // ART_COMPILER_OPTIMIZING_LOOP_ANALYSIS_H_ 184