130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik/* 230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * Copyright (C) 2015 The Android Open Source Project 330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * 430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * Licensed under the Apache License, Version 2.0 (the "License"); 530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * you may not use this file except in compliance with the License. 630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * You may obtain a copy of the License at 730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * 830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * http://www.apache.org/licenses/LICENSE-2.0 930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * 1030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * Unless required by applicable law or agreed to in writing, software 1130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * distributed under the License is distributed on an "AS IS" BASIS, 1230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * See the License for the specific language governing permissions and 1430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * limitations under the License. 1530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik */ 1630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 1730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 1830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 1930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#include <string> 2130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#include "nodes.h" 2330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#include "optimization.h" 2430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Biknamespace art { 2630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik/** 28e609b7cf9996389e6e693f149489737436172a2cAart Bik * Induction variable analysis. This class does not have a direct public API. 29e609b7cf9996389e6e693f149489737436172a2cAart Bik * Instead, the results of induction variable analysis can be queried through 30e609b7cf9996389e6e693f149489737436172a2cAart Bik * friend classes, such as InductionVarRange. 3130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * 32e609b7cf9996389e6e693f149489737436172a2cAart Bik * The analysis implementation is based on the paper by M. Gerlek et al. 3330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form" 3430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995). 3530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik */ 3630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bikclass HInductionVarAnalysis : public HOptimization { 3730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik public: 3830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik explicit HInductionVarAnalysis(HGraph* graph); 3930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 4030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void Run() OVERRIDE; 4130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 4230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik private: 4330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik static constexpr const char* kInductionPassName = "induction_var_analysis"; 4430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 4530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik struct NodeInfo { 4630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik explicit NodeInfo(uint32_t d) : depth(d), done(false) {} 4730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik uint32_t depth; 4830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik bool done; 4930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik }; 5030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 5130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik enum InductionClass { 5230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kInvariant, 5330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kLinear, 5430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kWrapAround, 55e609b7cf9996389e6e693f149489737436172a2cAart Bik kPeriodic 5630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik }; 5730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 5830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik enum InductionOp { 599401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // No-operation: a true induction. 609401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik kNop, 619401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // Various invariant operations. 6230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kAdd, 6330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kSub, 6430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kNeg, 6530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kMul, 6630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kDiv, 679401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik kFetch, 6822f058726d35dd8f40b3763649e61740b3d22535Aart Bik // Trip-counts. 6922f058726d35dd8f40b3763649e61740b3d22535Aart Bik kTripCountInLoop, // valid in full loop; loop is finite 7022f058726d35dd8f40b3763649e61740b3d22535Aart Bik kTripCountInBody, // valid in body only; loop is finite 7122f058726d35dd8f40b3763649e61740b3d22535Aart Bik kTripCountInLoopUnsafe, // valid in full loop; loop may be infinite 7222f058726d35dd8f40b3763649e61740b3d22535Aart Bik kTripCountInBodyUnsafe, // valid in body only; loop may be infinite 7322f058726d35dd8f40b3763649e61740b3d22535Aart Bik // Comparisons for trip-count tests. 7422f058726d35dd8f40b3763649e61740b3d22535Aart Bik kLT, 7522f058726d35dd8f40b3763649e61740b3d22535Aart Bik kLE, 7622f058726d35dd8f40b3763649e61740b3d22535Aart Bik kGT, 7722f058726d35dd8f40b3763649e61740b3d22535Aart Bik kGE 7830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik }; 7930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 8030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik /** 8130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * Defines a detected induction as: 8230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * (1) invariant: 8330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * operation: a + b, a - b, -b, a * b, a / b 84e609b7cf9996389e6e693f149489737436172a2cAart Bik * or: 8530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * fetch: fetch from HIR 8630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * (2) linear: 8730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * nop: a * i + b 8830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * (3) wrap-around 8930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * nop: a, then defined by b 9030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * (4) periodic 9130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * nop: a, then defined by b (repeated when exhausted) 929401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik * (5) trip-count: 9322f058726d35dd8f40b3763649e61740b3d22535Aart Bik * tc: defined by a, taken-test in b 9430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik */ 955233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> { 9630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo(InductionClass ic, 9730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionOp op, 9830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* a, 9930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* b, 1000d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* f, 1010d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type t) 10230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik : induction_class(ic), 10330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik operation(op), 10430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik op_a(a), 10530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik op_b(b), 1060d345cf8db01f40db250f80de5104e0df24234faAart Bik fetch(f), 1070d345cf8db01f40db250f80de5104e0df24234faAart Bik type(t) {} 10830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionClass induction_class; 10930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionOp operation; 11030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* op_a; 11130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* op_b; 11230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* fetch; 1130d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type; // precision of induction 11430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik }; 11530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 116e609b7cf9996389e6e693f149489737436172a2cAart Bik bool IsVisitedNode(HInstruction* instruction) const { 117e609b7cf9996389e6e693f149489737436172a2cAart Bik return map_.find(instruction) != map_.end(); 118e609b7cf9996389e6e693f149489737436172a2cAart Bik } 119e609b7cf9996389e6e693f149489737436172a2cAart Bik 120471a2034171346dda4539b985b95aa6370531171Aart Bik InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) { 121e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr); 122471a2034171346dda4539b985b95aa6370531171Aart Bik return CreateSimplifiedInvariant(op, a, b); 12330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 12430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 125471a2034171346dda4539b985b95aa6370531171Aart Bik InductionInfo* CreateInvariantFetch(HInstruction* f) { 126e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(f != nullptr); 1270d345cf8db01f40db250f80de5104e0df24234faAart Bik return new (graph_->GetArena()) 1280d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType()); 129e609b7cf9996389e6e693f149489737436172a2cAart Bik } 130e609b7cf9996389e6e693f149489737436172a2cAart Bik 1310d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* CreateTripCount(InductionOp op, 1320d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* a, 1330d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* b, 1340d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type) { 13522f058726d35dd8f40b3763649e61740b3d22535Aart Bik DCHECK(a != nullptr); 1360d345cf8db01f40db250f80de5104e0df24234faAart Bik return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type); 1379401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik } 1389401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik 1390d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* CreateInduction(InductionClass ic, 1400d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* a, 1410d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* b, 1420d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type) { 143e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(a != nullptr && b != nullptr); 1440d345cf8db01f40db250f80de5104e0df24234faAart Bik return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr, type); 14530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 14630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 14730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Methods for analysis. 14830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void VisitLoop(HLoopInformation* loop); 14930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void VisitNode(HLoopInformation* loop, HInstruction* instruction); 15030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction); 15130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction); 15230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void ClassifyNonTrivial(HLoopInformation* loop); 153f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last); 15430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 15530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Transfer operations. 156f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index); 15730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op); 15830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b); 159d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type); 16030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* TransferNeg(InductionInfo* a); 1610d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* TransferCnv(InductionInfo* a, Primitive::Type from, Primitive::Type to); 162e609b7cf9996389e6e693f149489737436172a2cAart Bik 163e609b7cf9996389e6e693f149489737436172a2cAart Bik // Solvers. 164f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* SolvePhi(HInstruction* phi, size_t input_index); 165f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* SolvePhiAllInputs(HLoopInformation* loop, 166f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* entry_phi, 167f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* phi); 168e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* SolveAddSub(HLoopInformation* loop, 169f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* entry_phi, 170e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* instruction, 171e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* x, 172e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* y, 173e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionOp op, 174e609b7cf9996389e6e693f149489737436172a2cAart Bik bool is_first_call); 1750d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* SolveCnv(HTypeConversion* conversion); 17630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 177d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Trip count information. 178d14c59564870c910bdc823081f0ed1101f599231Aart Bik void VisitControl(HLoopInformation* loop); 179d14c59564870c910bdc823081f0ed1101f599231Aart Bik void VisitCondition(HLoopInformation* loop, 180d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* a, 181d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* b, 182d14c59564870c910bdc823081f0ed1101f599231Aart Bik Primitive::Type type, 183d14c59564870c910bdc823081f0ed1101f599231Aart Bik IfCondition cmp); 184d14c59564870c910bdc823081f0ed1101f599231Aart Bik void VisitTripCount(HLoopInformation* loop, 1859401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik InductionInfo* lower_expr, 1869401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik InductionInfo* upper_expr, 187d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* stride, 1889401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t stride_value, 189d14c59564870c910bdc823081f0ed1101f599231Aart Bik Primitive::Type type, 190f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik IfCondition cmp); 1919401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp); 1929401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik bool IsFinite(InductionInfo* upper_expr, 1939401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t stride_value, 1949401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Primitive::Type type, 1959401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik IfCondition cmp); 1960d345cf8db01f40db250f80de5104e0df24234faAart Bik bool FitsNarrowerControl(InductionInfo* lower_expr, 1970d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* upper_expr, 1980d345cf8db01f40db250f80de5104e0df24234faAart Bik int64_t stride_value, 1990d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type, 2000d345cf8db01f40db250f80de5104e0df24234faAart Bik IfCondition cmp); 201d14c59564870c910bdc823081f0ed1101f599231Aart Bik 20230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Assign and lookup. 20330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); 20430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction); 205d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* CreateConstant(int64_t value, Primitive::Type type); 206471a2034171346dda4539b985b95aa6370531171Aart Bik InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b); 20730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2087d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // Constants. 20997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool IsExact(InductionInfo* info, /*out*/ int64_t* value); 21097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value); 21197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value); 2127d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik 213e609b7cf9996389e6e693f149489737436172a2cAart Bik // Helpers. 214e609b7cf9996389e6e693f149489737436172a2cAart Bik static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); 215e609b7cf9996389e6e693f149489737436172a2cAart Bik static std::string InductionToString(InductionInfo* info); 21630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 217e609b7cf9996389e6e693f149489737436172a2cAart Bik // TODO: fine tune the following data structures, only keep relevant data. 21830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 219e609b7cf9996389e6e693f149489737436172a2cAart Bik // Temporary book-keeping during the analysis. 220e609b7cf9996389e6e693f149489737436172a2cAart Bik uint32_t global_depth_; 22130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ArenaVector<HInstruction*> stack_; 22230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ArenaVector<HInstruction*> scc_; 223e609b7cf9996389e6e693f149489737436172a2cAart Bik ArenaSafeMap<HInstruction*, NodeInfo> map_; 224e609b7cf9996389e6e693f149489737436172a2cAart Bik ArenaSafeMap<HInstruction*, InductionInfo*> cycle_; 2250d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type_; 22630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 227e609b7cf9996389e6e693f149489737436172a2cAart Bik /** 228e609b7cf9996389e6e693f149489737436172a2cAart Bik * Maintains the results of the analysis as a mapping from loops to a mapping from instructions 229e609b7cf9996389e6e693f149489737436172a2cAart Bik * to the induction information for that instruction in that loop. 230e609b7cf9996389e6e693f149489737436172a2cAart Bik */ 231e609b7cf9996389e6e693f149489737436172a2cAart Bik ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_; 23230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 233e609b7cf9996389e6e693f149489737436172a2cAart Bik friend class InductionVarAnalysisTest; 234d14c59564870c910bdc823081f0ed1101f599231Aart Bik friend class InductionVarRange; 235d14c59564870c910bdc823081f0ed1101f599231Aart Bik friend class InductionVarRangeTest; 23630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 23730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis); 23830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik}; 23930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 24030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} // namespace art 24130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 24230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 243