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 static constexpr const char* kInductionPassName = "induction_var_analysis"; 4330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 445319d3cca5a9b8e9e3f59421818272b966575172Wojciech Staszkiewicz private: 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, 54c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik kPolynomial, 55c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik kGeometric, 5630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kWrapAround, 57e609b7cf9996389e6e693f149489737436172a2cAart Bik kPeriodic 5830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik }; 5930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 6030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik enum InductionOp { 61c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik // Operations. 629401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik kNop, 6330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kAdd, 6430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kSub, 6530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kNeg, 6630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kMul, 6730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik kDiv, 68df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik kRem, 697dc96932491dde6b5b58998254d5837dbcbbde03Aart Bik kXor, 709401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik kFetch, 7122f058726d35dd8f40b3763649e61740b3d22535Aart Bik // Trip-counts. 7222f058726d35dd8f40b3763649e61740b3d22535Aart Bik kTripCountInLoop, // valid in full loop; loop is finite 7322f058726d35dd8f40b3763649e61740b3d22535Aart Bik kTripCountInBody, // valid in body only; loop is finite 7422f058726d35dd8f40b3763649e61740b3d22535Aart Bik kTripCountInLoopUnsafe, // valid in full loop; loop may be infinite 7522f058726d35dd8f40b3763649e61740b3d22535Aart Bik kTripCountInBodyUnsafe, // valid in body only; loop may be infinite 7622f058726d35dd8f40b3763649e61740b3d22535Aart Bik // Comparisons for trip-count tests. 7722f058726d35dd8f40b3763649e61740b3d22535Aart Bik kLT, 7822f058726d35dd8f40b3763649e61740b3d22535Aart Bik kLE, 7922f058726d35dd8f40b3763649e61740b3d22535Aart Bik kGT, 8022f058726d35dd8f40b3763649e61740b3d22535Aart Bik kGE 8130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik }; 8230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 8330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik /** 8430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * Defines a detected induction as: 8530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * (1) invariant: 86c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik * op: a + b, a - b, -b, a * b, a / b, a % b, a ^ b, fetch 8730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * (2) linear: 8830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * nop: a * i + b 89df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik * (3) polynomial: 90df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik * nop: sum_lt(a) + b, for linear a 91c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik * (4) geometric: 92df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik * op: a * fetch^i + b, a * fetch^-i + b 93c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik * (5) wrap-around 9430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * nop: a, then defined by b 95c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik * (6) periodic 9630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * nop: a, then defined by b (repeated when exhausted) 97c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik * (7) trip-count: 9822f058726d35dd8f40b3763649e61740b3d22535Aart Bik * tc: defined by a, taken-test in b 9930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik */ 1005233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> { 10130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo(InductionClass ic, 10230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionOp op, 10330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* a, 10430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* b, 1050d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* f, 1060d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type t) 10730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik : induction_class(ic), 10830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik operation(op), 10930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik op_a(a), 11030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik op_b(b), 1110d345cf8db01f40db250f80de5104e0df24234faAart Bik fetch(f), 1120d345cf8db01f40db250f80de5104e0df24234faAart Bik type(t) {} 11330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionClass induction_class; 11430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionOp operation; 11530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* op_a; 11630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* op_b; 11730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* fetch; 118d0a022d76db4b79d105608e7bafab4c17e8ba510Aart Bik Primitive::Type type; // precision of operation 11930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik }; 12030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 121e609b7cf9996389e6e693f149489737436172a2cAart Bik bool IsVisitedNode(HInstruction* instruction) const { 122e609b7cf9996389e6e693f149489737436172a2cAart Bik return map_.find(instruction) != map_.end(); 123e609b7cf9996389e6e693f149489737436172a2cAart Bik } 124e609b7cf9996389e6e693f149489737436172a2cAart Bik 125471a2034171346dda4539b985b95aa6370531171Aart Bik InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) { 126e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr); 127471a2034171346dda4539b985b95aa6370531171Aart Bik return CreateSimplifiedInvariant(op, a, b); 12830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 12930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 130471a2034171346dda4539b985b95aa6370531171Aart Bik InductionInfo* CreateInvariantFetch(HInstruction* f) { 131e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(f != nullptr); 1320d345cf8db01f40db250f80de5104e0df24234faAart Bik return new (graph_->GetArena()) 1330d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType()); 134e609b7cf9996389e6e693f149489737436172a2cAart Bik } 135e609b7cf9996389e6e693f149489737436172a2cAart Bik 1360d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* CreateTripCount(InductionOp op, 1370d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* a, 1380d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* b, 1390d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type) { 14052be7e759acecc3841dca0ac1b703034d8cad60dAart Bik DCHECK(a != nullptr && b != nullptr); 1410d345cf8db01f40db250f80de5104e0df24234faAart Bik return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type); 1429401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik } 1439401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik 1440d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* CreateInduction(InductionClass ic, 145c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik InductionOp op, 1460d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* a, 1470d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* b, 148c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik HInstruction* f, 1490d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type) { 150e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(a != nullptr && b != nullptr); 151c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik return new (graph_->GetArena()) InductionInfo(ic, op, a, b, f, type); 15230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 15330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 15430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Methods for analysis. 15530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void VisitLoop(HLoopInformation* loop); 15630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void VisitNode(HLoopInformation* loop, HInstruction* instruction); 15730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction); 15830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction); 15930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void ClassifyNonTrivial(HLoopInformation* loop); 160f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last); 16130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 16230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Transfer operations. 163d0a022d76db4b79d105608e7bafab4c17e8ba510Aart Bik InductionInfo* TransferPhi(HLoopInformation* loop, 164d0a022d76db4b79d105608e7bafab4c17e8ba510Aart Bik HInstruction* phi, 165d0a022d76db4b79d105608e7bafab4c17e8ba510Aart Bik size_t input_index, 166d0a022d76db4b79d105608e7bafab4c17e8ba510Aart Bik size_t adjust_input_size); 16730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op); 16830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* TransferNeg(InductionInfo* a); 169c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b); 170e6bd0272b43bf73faabc64abc9c51ab8ed128308Aart Bik InductionInfo* TransferConversion(InductionInfo* a, Primitive::Type from, Primitive::Type to); 171e609b7cf9996389e6e693f149489737436172a2cAart Bik 172e609b7cf9996389e6e693f149489737436172a2cAart Bik // Solvers. 173d0a022d76db4b79d105608e7bafab4c17e8ba510Aart Bik InductionInfo* SolvePhi(HInstruction* phi, size_t input_index, size_t adjust_input_size); 174f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* SolvePhiAllInputs(HLoopInformation* loop, 175f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* entry_phi, 176f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* phi); 177e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* SolveAddSub(HLoopInformation* loop, 178f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* entry_phi, 179e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* instruction, 180e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* x, 181e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* y, 182e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionOp op, 1837dc96932491dde6b5b58998254d5837dbcbbde03Aart Bik bool is_first_call); // possibly swaps x and y to try again 184df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik InductionInfo* SolveOp(HLoopInformation* loop, 185df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik HInstruction* entry_phi, 186df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik HInstruction* instruction, 187df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik HInstruction* x, 188df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik HInstruction* y, 189df7822ecf033cecf48d950f3ae34f7043c8df738Aart Bik InductionOp op); 190639cc8c7bbb7d8c341173bcf24604ccb4328acb8Aart Bik InductionInfo* SolveTest(HLoopInformation* loop, 191639cc8c7bbb7d8c341173bcf24604ccb4328acb8Aart Bik HInstruction* entry_phi, 192639cc8c7bbb7d8c341173bcf24604ccb4328acb8Aart Bik HInstruction* instruction, 193639cc8c7bbb7d8c341173bcf24604ccb4328acb8Aart Bik int64_t oppositive_value); 194e6bd0272b43bf73faabc64abc9c51ab8ed128308Aart Bik InductionInfo* SolveConversion(HLoopInformation* loop, 195e6bd0272b43bf73faabc64abc9c51ab8ed128308Aart Bik HInstruction* entry_phi, 196e6bd0272b43bf73faabc64abc9c51ab8ed128308Aart Bik HTypeConversion* conversion); 19730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 198d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Trip count information. 199d14c59564870c910bdc823081f0ed1101f599231Aart Bik void VisitControl(HLoopInformation* loop); 200d14c59564870c910bdc823081f0ed1101f599231Aart Bik void VisitCondition(HLoopInformation* loop, 201d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* a, 202d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* b, 203d14c59564870c910bdc823081f0ed1101f599231Aart Bik Primitive::Type type, 204d14c59564870c910bdc823081f0ed1101f599231Aart Bik IfCondition cmp); 205d14c59564870c910bdc823081f0ed1101f599231Aart Bik void VisitTripCount(HLoopInformation* loop, 2069401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik InductionInfo* lower_expr, 2079401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik InductionInfo* upper_expr, 208d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* stride, 2099401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t stride_value, 210d14c59564870c910bdc823081f0ed1101f599231Aart Bik Primitive::Type type, 211f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik IfCondition cmp); 2129401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp); 2139401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik bool IsFinite(InductionInfo* upper_expr, 2149401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t stride_value, 2159401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Primitive::Type type, 2169401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik IfCondition cmp); 2170d345cf8db01f40db250f80de5104e0df24234faAart Bik bool FitsNarrowerControl(InductionInfo* lower_expr, 2180d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* upper_expr, 2190d345cf8db01f40db250f80de5104e0df24234faAart Bik int64_t stride_value, 2200d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type, 2210d345cf8db01f40db250f80de5104e0df24234faAart Bik IfCondition cmp); 222d14c59564870c910bdc823081f0ed1101f599231Aart Bik 22330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Assign and lookup. 22430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); 22530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction); 226d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* CreateConstant(int64_t value, Primitive::Type type); 227471a2034171346dda4539b985b95aa6370531171Aart Bik InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b); 228d0a022d76db4b79d105608e7bafab4c17e8ba510Aart Bik HInstruction* GetShiftConstant(HLoopInformation* loop, 229d0a022d76db4b79d105608e7bafab4c17e8ba510Aart Bik HInstruction* instruction, 230d0a022d76db4b79d105608e7bafab4c17e8ba510Aart Bik InductionInfo* initial); 231cc42be074ed15235426cdbcb34f357ead2be2cafAart Bik void AssignCycle(HPhi* phi); 232cc42be074ed15235426cdbcb34f357ead2be2cafAart Bik ArenaSet<HInstruction*>* LookupCycle(HPhi* phi); 23330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2347d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // Constants. 23597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool IsExact(InductionInfo* info, /*out*/ int64_t* value); 23697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value); 23797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value); 2387d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik 239e609b7cf9996389e6e693f149489737436172a2cAart Bik // Helpers. 240e6bd0272b43bf73faabc64abc9c51ab8ed128308Aart Bik static bool IsNarrowingLinear(InductionInfo* info); 241e609b7cf9996389e6e693f149489737436172a2cAart Bik static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); 242c071a01a26013ab6e3dbfc4131efa95a65aeb4edAart Bik static std::string FetchToString(HInstruction* fetch); 243e609b7cf9996389e6e693f149489737436172a2cAart Bik static std::string InductionToString(InductionInfo* info); 24430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 245e609b7cf9996389e6e693f149489737436172a2cAart Bik // TODO: fine tune the following data structures, only keep relevant data. 24630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 247e609b7cf9996389e6e693f149489737436172a2cAart Bik // Temporary book-keeping during the analysis. 248e609b7cf9996389e6e693f149489737436172a2cAart Bik uint32_t global_depth_; 24930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ArenaVector<HInstruction*> stack_; 250e609b7cf9996389e6e693f149489737436172a2cAart Bik ArenaSafeMap<HInstruction*, NodeInfo> map_; 2517dc96932491dde6b5b58998254d5837dbcbbde03Aart Bik ArenaVector<HInstruction*> scc_; 252e609b7cf9996389e6e693f149489737436172a2cAart Bik ArenaSafeMap<HInstruction*, InductionInfo*> cycle_; 2530d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type_; 25430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 255e609b7cf9996389e6e693f149489737436172a2cAart Bik /** 256e609b7cf9996389e6e693f149489737436172a2cAart Bik * Maintains the results of the analysis as a mapping from loops to a mapping from instructions 257e609b7cf9996389e6e693f149489737436172a2cAart Bik * to the induction information for that instruction in that loop. 258e609b7cf9996389e6e693f149489737436172a2cAart Bik */ 259e609b7cf9996389e6e693f149489737436172a2cAart Bik ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_; 26030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 261cc42be074ed15235426cdbcb34f357ead2be2cafAart Bik /** 262cc42be074ed15235426cdbcb34f357ead2be2cafAart Bik * Preserves induction cycle information for each loop-phi. 263cc42be074ed15235426cdbcb34f357ead2be2cafAart Bik */ 264cc42be074ed15235426cdbcb34f357ead2be2cafAart Bik ArenaSafeMap<HPhi*, ArenaSet<HInstruction*>> cycles_; 265cc42be074ed15235426cdbcb34f357ead2be2cafAart Bik 266e609b7cf9996389e6e693f149489737436172a2cAart Bik friend class InductionVarAnalysisTest; 267d14c59564870c910bdc823081f0ed1101f599231Aart Bik friend class InductionVarRange; 268d14c59564870c910bdc823081f0ed1101f599231Aart Bik friend class InductionVarRangeTest; 26930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 27030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis); 27130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik}; 27230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 27330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} // namespace art 27430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 27530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 276