Home | History | Annotate | Download | only in optimizing 
      1 /*
      2  * Copyright (C) 2015 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_INDUCTION_VAR_ANALYSIS_H_
     18 #define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
     19 
     20 #include <string>
     21 
     22 #include "nodes.h"
     23 #include "optimization.h"
     24 
     25 namespace art {
     26 
     27 /**
     28  * Induction variable analysis. This class does not have a direct public API.
     29  * Instead, the results of induction variable analysis can be queried through
     30  * friend classes, such as InductionVarRange.
     31  *
     32  * The analysis implementation is based on the paper by M. Gerlek et al.
     33  * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form"
     34  * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995).
     35  */
     36 class HInductionVarAnalysis : public HOptimization {
     37  public:
     38   explicit HInductionVarAnalysis(HGraph* graph);
     39 
     40   void Run() OVERRIDE;
     41 
     42  private:
     43   static constexpr const char* kInductionPassName = "induction_var_analysis";
     44 
     45   struct NodeInfo {
     46     explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
     47     uint32_t depth;
     48     bool done;
     49   };
     50 
     51   enum InductionClass {
     52     kInvariant,
     53     kLinear,
     54     kWrapAround,
     55     kPeriodic
     56   };
     57 
     58   enum InductionOp {
     59     // No-operation: a true induction.
     60     kNop,
     61     // Various invariant operations.
     62     kAdd,
     63     kSub,
     64     kNeg,
     65     kMul,
     66     kDiv,
     67     kFetch,
     68     // Trip-counts.
     69     kTripCountInLoop,        // valid in full loop; loop is finite
     70     kTripCountInBody,        // valid in body only; loop is finite
     71     kTripCountInLoopUnsafe,  // valid in full loop; loop may be infinite
     72     kTripCountInBodyUnsafe,  // valid in body only; loop may be infinite
     73     // Comparisons for trip-count tests.
     74     kLT,
     75     kLE,
     76     kGT,
     77     kGE
     78   };
     79 
     80   /**
     81    * Defines a detected induction as:
     82    *   (1) invariant:
     83    *         operation: a + b, a - b, -b, a * b, a / b
     84    *       or:
     85    *         fetch: fetch from HIR
     86    *   (2) linear:
     87    *         nop: a * i + b
     88    *   (3) wrap-around
     89    *         nop: a, then defined by b
     90    *   (4) periodic
     91    *         nop: a, then defined by b (repeated when exhausted)
     92    *   (5) trip-count:
     93    *         tc: defined by a, taken-test in b
     94    */
     95   struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> {
     96     InductionInfo(InductionClass ic,
     97                   InductionOp op,
     98                   InductionInfo* a,
     99                   InductionInfo* b,
    100                   HInstruction* f,
    101                   Primitive::Type t)
    102         : induction_class(ic),
    103           operation(op),
    104           op_a(a),
    105           op_b(b),
    106           fetch(f),
    107           type(t) {}
    108     InductionClass induction_class;
    109     InductionOp operation;
    110     InductionInfo* op_a;
    111     InductionInfo* op_b;
    112     HInstruction* fetch;
    113     Primitive::Type type;  // precision of induction
    114   };
    115 
    116   bool IsVisitedNode(HInstruction* instruction) const {
    117     return map_.find(instruction) != map_.end();
    118   }
    119 
    120   InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
    121     DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
    122     return CreateSimplifiedInvariant(op, a, b);
    123   }
    124 
    125   InductionInfo* CreateInvariantFetch(HInstruction* f) {
    126     DCHECK(f != nullptr);
    127     return new (graph_->GetArena())
    128         InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType());
    129   }
    130 
    131   InductionInfo* CreateTripCount(InductionOp op,
    132                                  InductionInfo* a,
    133                                  InductionInfo* b,
    134                                  Primitive::Type type) {
    135     DCHECK(a != nullptr);
    136     return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type);
    137   }
    138 
    139   InductionInfo* CreateInduction(InductionClass ic,
    140                                  InductionInfo* a,
    141                                  InductionInfo* b,
    142                                  Primitive::Type type) {
    143     DCHECK(a != nullptr && b != nullptr);
    144     return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr, type);
    145   }
    146 
    147   // Methods for analysis.
    148   void VisitLoop(HLoopInformation* loop);
    149   void VisitNode(HLoopInformation* loop, HInstruction* instruction);
    150   uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
    151   void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
    152   void ClassifyNonTrivial(HLoopInformation* loop);
    153   InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
    154 
    155   // Transfer operations.
    156   InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index);
    157   InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
    158   InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
    159   InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
    160   InductionInfo* TransferNeg(InductionInfo* a);
    161   InductionInfo* TransferCnv(InductionInfo* a, Primitive::Type from, Primitive::Type to);
    162 
    163   // Solvers.
    164   InductionInfo* SolvePhi(HInstruction* phi, size_t input_index);
    165   InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
    166                                    HInstruction* entry_phi,
    167                                    HInstruction* phi);
    168   InductionInfo* SolveAddSub(HLoopInformation* loop,
    169                              HInstruction* entry_phi,
    170                              HInstruction* instruction,
    171                              HInstruction* x,
    172                              HInstruction* y,
    173                              InductionOp op,
    174                              bool is_first_call);
    175   InductionInfo* SolveCnv(HTypeConversion* conversion);
    176 
    177   // Trip count information.
    178   void VisitControl(HLoopInformation* loop);
    179   void VisitCondition(HLoopInformation* loop,
    180                       InductionInfo* a,
    181                       InductionInfo* b,
    182                       Primitive::Type type,
    183                       IfCondition cmp);
    184   void VisitTripCount(HLoopInformation* loop,
    185                       InductionInfo* lower_expr,
    186                       InductionInfo* upper_expr,
    187                       InductionInfo* stride,
    188                       int64_t stride_value,
    189                       Primitive::Type type,
    190                       IfCondition cmp);
    191   bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp);
    192   bool IsFinite(InductionInfo* upper_expr,
    193                 int64_t stride_value,
    194                 Primitive::Type type,
    195                 IfCondition cmp);
    196   bool FitsNarrowerControl(InductionInfo* lower_expr,
    197                            InductionInfo* upper_expr,
    198                            int64_t stride_value,
    199                            Primitive::Type type,
    200                            IfCondition cmp);
    201 
    202   // Assign and lookup.
    203   void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
    204   InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
    205   InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
    206   InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
    207 
    208   // Constants.
    209   bool IsExact(InductionInfo* info, /*out*/ int64_t* value);
    210   bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value);
    211   bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value);
    212 
    213   // Helpers.
    214   static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
    215   static std::string InductionToString(InductionInfo* info);
    216 
    217   // TODO: fine tune the following data structures, only keep relevant data.
    218 
    219   // Temporary book-keeping during the analysis.
    220   uint32_t global_depth_;
    221   ArenaVector<HInstruction*> stack_;
    222   ArenaVector<HInstruction*> scc_;
    223   ArenaSafeMap<HInstruction*, NodeInfo> map_;
    224   ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
    225   Primitive::Type type_;
    226 
    227   /**
    228    * Maintains the results of the analysis as a mapping from loops to a mapping from instructions
    229    * to the induction information for that instruction in that loop.
    230    */
    231   ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
    232 
    233   friend class InductionVarAnalysisTest;
    234   friend class InductionVarRange;
    235   friend class InductionVarRangeTest;
    236 
    237   DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
    238 };
    239 
    240 }  // namespace art
    241 
    242 #endif  // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
    243