Home | History | Annotate | Download | only in optimizing 
      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