1d14c59564870c910bdc823081f0ed1101f599231Aart Bik/* 2d14c59564870c910bdc823081f0ed1101f599231Aart Bik * Copyright (C) 2015 The Android Open Source Project 3d14c59564870c910bdc823081f0ed1101f599231Aart Bik * 4d14c59564870c910bdc823081f0ed1101f599231Aart Bik * Licensed under the Apache License, Version 2.0 (the "License"); 5d14c59564870c910bdc823081f0ed1101f599231Aart Bik * you may not use this file except in compliance with the License. 6d14c59564870c910bdc823081f0ed1101f599231Aart Bik * You may obtain a copy of the License at 7d14c59564870c910bdc823081f0ed1101f599231Aart Bik * 8d14c59564870c910bdc823081f0ed1101f599231Aart Bik * http://www.apache.org/licenses/LICENSE-2.0 9d14c59564870c910bdc823081f0ed1101f599231Aart Bik * 10d14c59564870c910bdc823081f0ed1101f599231Aart Bik * Unless required by applicable law or agreed to in writing, software 11d14c59564870c910bdc823081f0ed1101f599231Aart Bik * distributed under the License is distributed on an "AS IS" BASIS, 12d14c59564870c910bdc823081f0ed1101f599231Aart Bik * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13d14c59564870c910bdc823081f0ed1101f599231Aart Bik * See the License for the specific language governing permissions and 14d14c59564870c910bdc823081f0ed1101f599231Aart Bik * limitations under the License. 15d14c59564870c910bdc823081f0ed1101f599231Aart Bik */ 16d14c59564870c910bdc823081f0ed1101f599231Aart Bik 17d14c59564870c910bdc823081f0ed1101f599231Aart Bik#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ 18d14c59564870c910bdc823081f0ed1101f599231Aart Bik#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ 19d14c59564870c910bdc823081f0ed1101f599231Aart Bik 20d14c59564870c910bdc823081f0ed1101f599231Aart Bik#include "induction_var_analysis.h" 21d14c59564870c910bdc823081f0ed1101f599231Aart Bik 22d14c59564870c910bdc823081f0ed1101f599231Aart Biknamespace art { 23d14c59564870c910bdc823081f0ed1101f599231Aart Bik 24d14c59564870c910bdc823081f0ed1101f599231Aart Bik/** 25b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * This class implements range analysis on expressions within loops. It takes the results 26b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * of induction variable analysis in the constructor and provides a public API to obtain 27b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * a conservative lower and upper bound value on each instruction in the HIR. 28d14c59564870c910bdc823081f0ed1101f599231Aart Bik * 29b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * The range analysis is done with a combination of symbolic and partial integral evaluation 30b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * of expressions. The analysis avoids complications with wrap-around arithmetic on the integral 31b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * parts but all clients should be aware that wrap-around may occur on any of the symbolic parts. 32b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * For example, given a known range for [0,100] for i, the evaluation yields range [-100,100] 33b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * for expression -2*i+100, which is exact, and range [x,x+100] for expression i+x, which may 34b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * wrap-around anywhere in the range depending on the actual value of x. 35d14c59564870c910bdc823081f0ed1101f599231Aart Bik */ 36d14c59564870c910bdc823081f0ed1101f599231Aart Bikclass InductionVarRange { 37d14c59564870c910bdc823081f0ed1101f599231Aart Bik public: 38d14c59564870c910bdc823081f0ed1101f599231Aart Bik /* 39d14c59564870c910bdc823081f0ed1101f599231Aart Bik * A value that can be represented as "a * instruction + b" for 32-bit constants, where 40b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * Value() denotes an unknown lower and upper bound. Although range analysis could yield 41b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * more complex values, the format is sufficiently powerful to represent useful cases 42b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * and feeds directly into optimizations like bounds check elimination. 43d14c59564870c910bdc823081f0ed1101f599231Aart Bik */ 44d14c59564870c910bdc823081f0ed1101f599231Aart Bik struct Value { 45b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik Value() : instruction(nullptr), a_constant(0), b_constant(0), is_known(false) {} 46d14c59564870c910bdc823081f0ed1101f599231Aart Bik Value(HInstruction* i, int32_t a, int32_t b) 47b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik : instruction(a != 0 ? i : nullptr), a_constant(a), b_constant(b), is_known(true) {} 48d14c59564870c910bdc823081f0ed1101f599231Aart Bik explicit Value(int32_t b) : Value(nullptr, 0, b) {} 49b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik // Representation as: a_constant x instruction + b_constant. 50d14c59564870c910bdc823081f0ed1101f599231Aart Bik HInstruction* instruction; 51d14c59564870c910bdc823081f0ed1101f599231Aart Bik int32_t a_constant; 52d14c59564870c910bdc823081f0ed1101f599231Aart Bik int32_t b_constant; 53b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik // If true, represented by prior fields. Otherwise unknown value. 54b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik bool is_known; 55d14c59564870c910bdc823081f0ed1101f599231Aart Bik }; 56d14c59564870c910bdc823081f0ed1101f599231Aart Bik 57d14c59564870c910bdc823081f0ed1101f599231Aart Bik explicit InductionVarRange(HInductionVarAnalysis* induction); 58d14c59564870c910bdc823081f0ed1101f599231Aart Bik 59d14c59564870c910bdc823081f0ed1101f599231Aart Bik /** 60389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * Given a context denoted by the first instruction, returns a possibly conservative 61389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * lower and upper bound on the instruction's value in the output parameters min_val 62389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * and max_val, respectively. The need_finite_test flag denotes if an additional finite-test 631fc3afb76dbed78d255db276381df6036db2ee98Aart Bik * is needed to protect the range evaluation inside its loop. Returns false on failure. 64d14c59564870c910bdc823081f0ed1101f599231Aart Bik */ 651fc3afb76dbed78d255db276381df6036db2ee98Aart Bik bool GetInductionRange(HInstruction* context, 66389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HInstruction* instruction, 671fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ Value* min_val, 681fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ Value* max_val, 691fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ bool* needs_finite_test); 70d14c59564870c910bdc823081f0ed1101f599231Aart Bik 71b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik /** Refines the values with induction of next outer loop. Returns true on change. */ 7297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool RefineOuter(/*in-out*/ Value* min_val, 7397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik /*in-out*/ Value* max_val) const; 74b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik 75d14c59564870c910bdc823081f0ed1101f599231Aart Bik /** 76389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * Returns true if range analysis is able to generate code for the lower and upper 77389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * bound expressions on the instruction in the given context. The need_finite_test 78389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * and need_taken test flags denote if an additional finite-test and/or taken-test 79389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * are needed to protect the range evaluation inside its loop. 80d14c59564870c910bdc823081f0ed1101f599231Aart Bik */ 81389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik bool CanGenerateCode(HInstruction* context, 82389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HInstruction* instruction, 831fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ bool* needs_finite_test, 841fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ bool* needs_taken_test); 85aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik 86aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik /** 87aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * Generates the actual code in the HIR for the lower and upper bound expressions on the 88aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * instruction in the given context. Code for the lower and upper bound expression are 89389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * generated in given block and graph and are returned in the output parameters lower and 90389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * upper, respectively. For a loop invariant, lower is not set. 91aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * 92aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * For example, given expression x+i with range [0, 5] for i, calling this method 93aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * will generate the following sequence: 94aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * 95aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * block: 96aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * lower: add x, 0 97aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * upper: add x, 5 98389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * 99389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * Precondition: CanGenerateCode() returns true. 100aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik */ 101389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik void GenerateRangeCode(HInstruction* context, 102389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HInstruction* instruction, 103389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HGraph* graph, 104389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HBasicBlock* block, 1051fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ HInstruction** lower, 1061fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ HInstruction** upper); 107389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik 108389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /** 109389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * Generates explicit taken-test for the loop in the given context. Code is generated in 110389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * given block and graph. The taken-test is returned in parameter test. 111389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * 112389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * Precondition: CanGenerateCode() returns true and needs_taken_test is set. 113389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik */ 114389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik void GenerateTakenTest(HInstruction* context, 115389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HGraph* graph, 116389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HBasicBlock* block, 1171fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ HInstruction** taken_test); 118aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik 119d14c59564870c910bdc823081f0ed1101f599231Aart Bik private: 12097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik /* 12197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik * Enum used in IsConstant() request. 12297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik */ 12397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik enum ConstantRequest { 12497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik kExact, 12597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik kAtMost, 12697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik kAtLeast 12797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik }; 12897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik 12997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik /** 13097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik * Returns true if exact or upper/lower bound on the given induction 13197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik * information is known as a 64-bit constant, which is returned in value. 13297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik */ 13397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool IsConstant(HInductionVarAnalysis::InductionInfo* info, 13497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik ConstantRequest request, 13597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik /*out*/ int64_t *value) const; 13697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik 1377d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const; 1387d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const; 1397d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const; 1407d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik 1417d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value GetLinear(HInductionVarAnalysis::InductionInfo* info, 1427d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* trip, 1437d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool in_body, 1447d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const; 1457d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value GetFetch(HInstruction* instruction, 1467d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* trip, 1477d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool in_body, 1487d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const; 1497d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value GetVal(HInductionVarAnalysis::InductionInfo* info, 1507d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* trip, 1517d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool in_body, 1527d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const; 1537d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value GetMul(HInductionVarAnalysis::InductionInfo* info1, 1547d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* info2, 1557d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* trip, 1567d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool in_body, 1577d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const; 1587d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, 1597d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* info2, 1607d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* trip, 1617d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool in_body, 1627d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const; 1637d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik 16497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik Value MulRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const; 16597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik Value DivRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const; 1667d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik 1677d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value AddValue(Value v1, Value v2) const; 1687d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value SubValue(Value v1, Value v2) const; 1697d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value MulValue(Value v1, Value v2) const; 1707d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value DivValue(Value v1, Value v2) const; 1717d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value MergeVal(Value v1, Value v2, bool is_min) const; 172d14c59564870c910bdc823081f0ed1101f599231Aart Bik 173aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik /** 174b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik * Returns refined value using induction of next outer loop or the input value if no 175b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik * further refinement is possible. 176b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik */ 1777d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik Value RefineOuter(Value val, bool is_min) const; 178b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik 179b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik /** 180389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * Generates code for lower/upper/taken-test in the HIR. Returns true on success. 181389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik * With values nullptr, the method can be used to determine if code generation 182aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik * would be successful without generating actual code yet. 183aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik */ 184aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik bool GenerateCode(HInstruction* context, 185aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HInstruction* instruction, 186aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HGraph* graph, 187aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HBasicBlock* block, 1881fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ HInstruction** lower, 1891fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ HInstruction** upper, 1901fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ HInstruction** taken_test, 1911fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ bool* needs_finite_test, 1921fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ bool* needs_taken_test) const; 1937d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik 1947d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool GenerateCode(HInductionVarAnalysis::InductionInfo* info, 1957d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* trip, 1967d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HGraph* graph, 1977d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HBasicBlock* block, 1981fc3afb76dbed78d255db276381df6036db2ee98Aart Bik /*out*/ HInstruction** result, 1997d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool in_body, 2007d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const; 201aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik 202d14c59564870c910bdc823081f0ed1101f599231Aart Bik /** Results of prior induction variable analysis. */ 203d14c59564870c910bdc823081f0ed1101f599231Aart Bik HInductionVarAnalysis *induction_analysis_; 204d14c59564870c910bdc823081f0ed1101f599231Aart Bik 20522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik friend class HInductionVarAnalysis; 206d14c59564870c910bdc823081f0ed1101f599231Aart Bik friend class InductionVarRangeTest; 207d14c59564870c910bdc823081f0ed1101f599231Aart Bik 208d14c59564870c910bdc823081f0ed1101f599231Aart Bik DISALLOW_COPY_AND_ASSIGN(InductionVarRange); 209d14c59564870c910bdc823081f0ed1101f599231Aart Bik}; 210d14c59564870c910bdc823081f0ed1101f599231Aart Bik 211d14c59564870c910bdc823081f0ed1101f599231Aart Bik} // namespace art 212d14c59564870c910bdc823081f0ed1101f599231Aart Bik 213d14c59564870c910bdc823081f0ed1101f599231Aart Bik#endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ 214