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#include "induction_var_range.h" 18d14c59564870c910bdc823081f0ed1101f599231Aart Bik 19cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik#include <limits> 20cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik 21d14c59564870c910bdc823081f0ed1101f599231Aart Biknamespace art { 22d14c59564870c910bdc823081f0ed1101f599231Aart Bik 23b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik/** Returns true if 64-bit constant fits in 32-bit constant. */ 24b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bikstatic bool CanLongValueFitIntoInt(int64_t c) { 25cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik return std::numeric_limits<int32_t>::min() <= c && c <= std::numeric_limits<int32_t>::max(); 26d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 27d14c59564870c910bdc823081f0ed1101f599231Aart Bik 28b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik/** Returns true if 32-bit addition can be done safely. */ 29d14c59564870c910bdc823081f0ed1101f599231Aart Bikstatic bool IsSafeAdd(int32_t c1, int32_t c2) { 30b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return CanLongValueFitIntoInt(static_cast<int64_t>(c1) + static_cast<int64_t>(c2)); 31d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 32d14c59564870c910bdc823081f0ed1101f599231Aart Bik 33b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik/** Returns true if 32-bit subtraction can be done safely. */ 34d14c59564870c910bdc823081f0ed1101f599231Aart Bikstatic bool IsSafeSub(int32_t c1, int32_t c2) { 35b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return CanLongValueFitIntoInt(static_cast<int64_t>(c1) - static_cast<int64_t>(c2)); 36d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 37d14c59564870c910bdc823081f0ed1101f599231Aart Bik 38b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik/** Returns true if 32-bit multiplication can be done safely. */ 39d14c59564870c910bdc823081f0ed1101f599231Aart Bikstatic bool IsSafeMul(int32_t c1, int32_t c2) { 40b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return CanLongValueFitIntoInt(static_cast<int64_t>(c1) * static_cast<int64_t>(c2)); 41d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 42d14c59564870c910bdc823081f0ed1101f599231Aart Bik 43b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik/** Returns true if 32-bit division can be done safely. */ 44d14c59564870c910bdc823081f0ed1101f599231Aart Bikstatic bool IsSafeDiv(int32_t c1, int32_t c2) { 45b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return c2 != 0 && CanLongValueFitIntoInt(static_cast<int64_t>(c1) / static_cast<int64_t>(c2)); 46d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 47d14c59564870c910bdc823081f0ed1101f599231Aart Bik 4897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik/** Returns true for 32/64-bit constant instruction. */ 4997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bikstatic bool IsIntAndGet(HInstruction* instruction, int64_t* value) { 50d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (instruction->IsIntConstant()) { 51b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik *value = instruction->AsIntConstant()->GetValue(); 52b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return true; 53d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (instruction->IsLongConstant()) { 5497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik *value = instruction->AsLongConstant()->GetValue(); 5597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return true; 56d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 57d14c59564870c910bdc823081f0ed1101f599231Aart Bik return false; 58d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 59d14c59564870c910bdc823081f0ed1101f599231Aart Bik 60b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik/** 610d345cf8db01f40db250f80de5104e0df24234faAart Bik * An upper bound a * (length / a) + b, where a >= 1, can be conservatively rewritten as length + b 62b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik * because length >= 0 is true. This makes it more likely the bound is useful to clients. 63b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik */ 64b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bikstatic InductionVarRange::Value SimplifyMax(InductionVarRange::Value v) { 6597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik int64_t value; 6697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (v.is_known && 670d345cf8db01f40db250f80de5104e0df24234faAart Bik v.a_constant >= 1 && 68b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik v.instruction->IsDiv() && 69b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik v.instruction->InputAt(0)->IsArrayLength() && 70b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik IsIntAndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) { 71b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return InductionVarRange::Value(v.instruction->InputAt(0), 1, v.b_constant); 72b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik } 73b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return v; 74b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik} 75b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik 760d345cf8db01f40db250f80de5104e0df24234faAart Bik/** 770d345cf8db01f40db250f80de5104e0df24234faAart Bik * Corrects a value for type to account for arithmetic wrap-around in lower precision. 780d345cf8db01f40db250f80de5104e0df24234faAart Bik */ 790d345cf8db01f40db250f80de5104e0df24234faAart Bikstatic InductionVarRange::Value CorrectForType(InductionVarRange::Value v, Primitive::Type type) { 800d345cf8db01f40db250f80de5104e0df24234faAart Bik switch (type) { 810d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimShort: 820d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimChar: 830d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimByte: { 840d345cf8db01f40db250f80de5104e0df24234faAart Bik // Constants within range only. 850d345cf8db01f40db250f80de5104e0df24234faAart Bik // TODO: maybe some room for improvement, like allowing widening conversions 860d345cf8db01f40db250f80de5104e0df24234faAart Bik const int32_t min = Primitive::MinValueOfIntegralType(type); 870d345cf8db01f40db250f80de5104e0df24234faAart Bik const int32_t max = Primitive::MaxValueOfIntegralType(type); 880d345cf8db01f40db250f80de5104e0df24234faAart Bik return (v.is_known && v.a_constant == 0 && min <= v.b_constant && v.b_constant <= max) 890d345cf8db01f40db250f80de5104e0df24234faAart Bik ? v 900d345cf8db01f40db250f80de5104e0df24234faAart Bik : InductionVarRange::Value(); 910d345cf8db01f40db250f80de5104e0df24234faAart Bik } 920d345cf8db01f40db250f80de5104e0df24234faAart Bik default: 930d345cf8db01f40db250f80de5104e0df24234faAart Bik // At int or higher. 940d345cf8db01f40db250f80de5104e0df24234faAart Bik return v; 950d345cf8db01f40db250f80de5104e0df24234faAart Bik } 960d345cf8db01f40db250f80de5104e0df24234faAart Bik} 970d345cf8db01f40db250f80de5104e0df24234faAart Bik 9897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik/** Helper method to test for a constant value. */ 9997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bikstatic bool IsConstantValue(InductionVarRange::Value v) { 10097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return v.is_known && v.a_constant == 0; 10197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik} 10297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik 10397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik/** Helper method to test for same constant value. */ 10497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bikstatic bool IsSameConstantValue(InductionVarRange::Value v1, InductionVarRange::Value v2) { 10597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return IsConstantValue(v1) && IsConstantValue(v2) && v1.b_constant == v2.b_constant; 10697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik} 10797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik 108389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik/** Helper method to insert an instruction. */ 109389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bikstatic HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { 110389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik DCHECK(block != nullptr); 111389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik DCHECK(block->GetLastInstruction() != nullptr) << block->GetBlockId(); 112aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik DCHECK(instruction != nullptr); 113389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik block->InsertInstructionBefore(instruction, block->GetLastInstruction()); 114aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik return instruction; 115aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik} 116aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik 117d14c59564870c910bdc823081f0ed1101f599231Aart Bik// 118d14c59564870c910bdc823081f0ed1101f599231Aart Bik// Public class methods. 119d14c59564870c910bdc823081f0ed1101f599231Aart Bik// 120d14c59564870c910bdc823081f0ed1101f599231Aart Bik 121d14c59564870c910bdc823081f0ed1101f599231Aart BikInductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis) 122d14c59564870c910bdc823081f0ed1101f599231Aart Bik : induction_analysis_(induction_analysis) { 123b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik DCHECK(induction_analysis != nullptr); 124d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 125d14c59564870c910bdc823081f0ed1101f599231Aart Bik 1261fc3afb76dbed78d255db276381df6036db2ee98Aart Bikbool InductionVarRange::GetInductionRange(HInstruction* context, 127389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HInstruction* instruction, 128389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/Value* min_val, 129389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/Value* max_val, 130389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/bool* needs_finite_test) { 131389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop 13297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (loop == nullptr) { 13397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return false; // no loop 13497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 13597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction); 13697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (info == nullptr) { 13797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return false; // no induction information 138389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 1390d345cf8db01f40db250f80de5104e0df24234faAart Bik // Type int or lower (this is not too restrictive since intended clients, like 1400d345cf8db01f40db250f80de5104e0df24234faAart Bik // bounds check elimination, will have truncated higher precision induction 1410d345cf8db01f40db250f80de5104e0df24234faAart Bik // at their use point already). 1420d345cf8db01f40db250f80de5104e0df24234faAart Bik switch (info->type) { 1430d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimInt: 1440d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimShort: 1450d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimChar: 1460d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimByte: 1470d345cf8db01f40db250f80de5104e0df24234faAart Bik break; 1480d345cf8db01f40db250f80de5104e0df24234faAart Bik default: 1490d345cf8db01f40db250f80de5104e0df24234faAart Bik return false; 1500d345cf8db01f40db250f80de5104e0df24234faAart Bik } 15197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Set up loop information. 15297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HBasicBlock* header = loop->GetHeader(); 15397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool in_body = context->GetBlock() != header; 15497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HInductionVarAnalysis::InductionInfo* trip = 15597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); 15697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Find range. 15797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik *min_val = GetVal(info, trip, in_body, /* is_min */ true); 15897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false)); 15997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip); 16097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return true; 161d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 162d14c59564870c910bdc823081f0ed1101f599231Aart Bik 16397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bikbool InductionVarRange::RefineOuter(/*in-out*/ Value* min_val, 16497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik /*in-out*/ Value* max_val) const { 1650d345cf8db01f40db250f80de5104e0df24234faAart Bik if (min_val->instruction != nullptr || max_val->instruction != nullptr) { 1660d345cf8db01f40db250f80de5104e0df24234faAart Bik Value v1_min = RefineOuter(*min_val, /* is_min */ true); 1670d345cf8db01f40db250f80de5104e0df24234faAart Bik Value v2_max = RefineOuter(*max_val, /* is_min */ false); 1680d345cf8db01f40db250f80de5104e0df24234faAart Bik // The refined range is safe if both sides refine the same instruction. Otherwise, since two 1690d345cf8db01f40db250f80de5104e0df24234faAart Bik // different ranges are combined, the new refined range is safe to pass back to the client if 1700d345cf8db01f40db250f80de5104e0df24234faAart Bik // the extremes of the computed ranges ensure no arithmetic wrap-around anomalies occur. 1710d345cf8db01f40db250f80de5104e0df24234faAart Bik if (min_val->instruction != max_val->instruction) { 1720d345cf8db01f40db250f80de5104e0df24234faAart Bik Value v1_max = RefineOuter(*min_val, /* is_min */ false); 1730d345cf8db01f40db250f80de5104e0df24234faAart Bik Value v2_min = RefineOuter(*max_val, /* is_min */ true); 1740d345cf8db01f40db250f80de5104e0df24234faAart Bik if (!IsConstantValue(v1_max) || 1750d345cf8db01f40db250f80de5104e0df24234faAart Bik !IsConstantValue(v2_min) || 1760d345cf8db01f40db250f80de5104e0df24234faAart Bik v1_max.b_constant > v2_min.b_constant) { 1770d345cf8db01f40db250f80de5104e0df24234faAart Bik return false; 1780d345cf8db01f40db250f80de5104e0df24234faAart Bik } 1790d345cf8db01f40db250f80de5104e0df24234faAart Bik } 1800d345cf8db01f40db250f80de5104e0df24234faAart Bik // Did something change? 1810d345cf8db01f40db250f80de5104e0df24234faAart Bik if (v1_min.instruction != min_val->instruction || v2_max.instruction != max_val->instruction) { 1820d345cf8db01f40db250f80de5104e0df24234faAart Bik *min_val = v1_min; 1830d345cf8db01f40db250f80de5104e0df24234faAart Bik *max_val = v2_max; 1840d345cf8db01f40db250f80de5104e0df24234faAart Bik return true; 18597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 186b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik } 187b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik return false; 188b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik} 189b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik 190aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bikbool InductionVarRange::CanGenerateCode(HInstruction* context, 191aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HInstruction* instruction, 192389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/bool* needs_finite_test, 193389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/bool* needs_taken_test) { 194389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik return GenerateCode(context, 195389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik instruction, 196389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik nullptr, nullptr, nullptr, nullptr, nullptr, // nothing generated yet 197389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik needs_finite_test, 198389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik needs_taken_test); 199aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik} 200aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik 201389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bikvoid InductionVarRange::GenerateRangeCode(HInstruction* context, 202389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HInstruction* instruction, 203389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HGraph* graph, 204389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HBasicBlock* block, 205389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/HInstruction** lower, 206389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/HInstruction** upper) { 207389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik bool b1, b2; // unused 208389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik if (!GenerateCode(context, instruction, graph, block, lower, upper, nullptr, &b1, &b2)) { 209389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik LOG(FATAL) << "Failed precondition: GenerateCode()"; 210389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 211389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik} 212389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik 213389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bikvoid InductionVarRange::GenerateTakenTest(HInstruction* context, 214389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HGraph* graph, 215389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HBasicBlock* block, 216389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/HInstruction** taken_test) { 217389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik bool b1, b2; // unused 218389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik if (!GenerateCode(context, context, graph, block, nullptr, nullptr, taken_test, &b1, &b2)) { 219389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik LOG(FATAL) << "Failed precondition: GenerateCode()"; 220389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 221aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik} 222aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik 223d14c59564870c910bdc823081f0ed1101f599231Aart Bik// 224d14c59564870c910bdc823081f0ed1101f599231Aart Bik// Private class methods. 225d14c59564870c910bdc823081f0ed1101f599231Aart Bik// 226d14c59564870c910bdc823081f0ed1101f599231Aart Bik 22797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bikbool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, 22897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik ConstantRequest request, 22997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik /*out*/ int64_t *value) const { 23097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (info != nullptr) { 23197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // A direct 32-bit or 64-bit constant fetch. This immediately satisfies 23297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // any of the three requests (kExact, kAtMost, and KAtLeast). 23397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (info->induction_class == HInductionVarAnalysis::kInvariant && 23497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik info->operation == HInductionVarAnalysis::kFetch) { 23597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsIntAndGet(info->fetch, value)) { 23697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return true; 23797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 23897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 23997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Try range analysis while traversing outward on loops. 24097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool in_body = true; // no known trip count 24197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik Value v_min = GetVal(info, nullptr, in_body, /* is_min */ true); 24297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik Value v_max = GetVal(info, nullptr, in_body, /* is_min */ false); 24397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik do { 24497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Make sure *both* extremes are known to avoid arithmetic wrap-around anomalies. 24597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(v_min) && IsConstantValue(v_max) && v_min.b_constant <= v_max.b_constant) { 24697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if ((request == kExact && v_min.b_constant == v_max.b_constant) || request == kAtMost) { 24797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik *value = v_max.b_constant; 24897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return true; 24997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } else if (request == kAtLeast) { 25097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik *value = v_min.b_constant; 25197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return true; 25297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 25397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 25497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } while (RefineOuter(&v_min, &v_max)); 255358af839c60db9e178f0b0bb9d430711c071b82aAart Bik // Exploit array length + c >= c, with c <= 0 to avoid arithmetic wrap-around anomalies 256358af839c60db9e178f0b0bb9d430711c071b82aAart Bik // (e.g. array length == maxint and c == 1 would yield minint). 257358af839c60db9e178f0b0bb9d430711c071b82aAart Bik if (request == kAtLeast) { 258358af839c60db9e178f0b0bb9d430711c071b82aAart Bik if (v_min.a_constant == 1 && v_min.b_constant <= 0 && v_min.instruction->IsArrayLength()) { 259358af839c60db9e178f0b0bb9d430711c071b82aAart Bik *value = v_min.b_constant; 260358af839c60db9e178f0b0bb9d430711c071b82aAart Bik return true; 261358af839c60db9e178f0b0bb9d430711c071b82aAart Bik } 262358af839c60db9e178f0b0bb9d430711c071b82aAart Bik } 26397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 26497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return false; 26597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik} 26697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik 2677d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bikbool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const { 268389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik if (info != nullptr) { 269389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik if (info->induction_class == HInductionVarAnalysis::kLinear) { 270389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik return true; 271389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) { 272389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik return NeedsTripCount(info->op_b); 273389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 274d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 275389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik return false; 276389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik} 277389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik 2787d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bikbool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const { 279389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik if (trip != nullptr) { 280389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik if (trip->induction_class == HInductionVarAnalysis::kInvariant) { 281389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik return trip->operation == HInductionVarAnalysis::kTripCountInBody || 282389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe; 283389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 284389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 285389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik return false; 286389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik} 287389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik 2887d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bikbool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const { 289389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik if (trip != nullptr) { 290389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik if (trip->induction_class == HInductionVarAnalysis::kInvariant) { 291389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe || 292389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik trip->operation == HInductionVarAnalysis::kTripCountInLoopUnsafe; 293389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 294389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 295389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik return false; 296d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 297d14c59564870c910bdc823081f0ed1101f599231Aart Bik 2987d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart BikInductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info, 2997d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* trip, 3007d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool in_body, 3017d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const { 3027d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // Detect common situation where an offset inside the trip count cancels out during range 3037d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding 3047d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information 3057d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // with intermediate results that only incorporate single instructions. 3067d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik if (trip != nullptr) { 3077d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a; 3087d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik if (trip_expr->operation == HInductionVarAnalysis::kSub) { 30997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik int64_t stride_value = 0; 31097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstant(info->op_a, kExact, &stride_value)) { 3117d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik if (!is_min && stride_value == 1) { 31297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Test original trip's negative operand (trip_expr->op_b) against offset of induction. 3137d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) { 3147d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // Analyze cancelled trip with just the positive operand (trip_expr->op_a). 3157d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo cancelled_trip( 3160d345cf8db01f40db250f80de5104e0df24234faAart Bik trip->induction_class, 3170d345cf8db01f40db250f80de5104e0df24234faAart Bik trip->operation, 3180d345cf8db01f40db250f80de5104e0df24234faAart Bik trip_expr->op_a, 3190d345cf8db01f40db250f80de5104e0df24234faAart Bik trip->op_b, 3200d345cf8db01f40db250f80de5104e0df24234faAart Bik nullptr, 3210d345cf8db01f40db250f80de5104e0df24234faAart Bik trip->type); 3227d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return GetVal(&cancelled_trip, trip, in_body, is_min); 3237d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } 3247d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } else if (is_min && stride_value == -1) { 32597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Test original trip's positive operand (trip_expr->op_a) against offset of induction. 3267d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik if (HInductionVarAnalysis::InductionEqual(trip_expr->op_a, info->op_b)) { 3277d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // Analyze cancelled trip with just the negative operand (trip_expr->op_b). 3287d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo neg( 3297d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::kInvariant, 3307d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::kNeg, 3317d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik nullptr, 3327d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik trip_expr->op_b, 3330d345cf8db01f40db250f80de5104e0df24234faAart Bik nullptr, 3340d345cf8db01f40db250f80de5104e0df24234faAart Bik trip->type); 3357d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik HInductionVarAnalysis::InductionInfo cancelled_trip( 3360d345cf8db01f40db250f80de5104e0df24234faAart Bik trip->induction_class, trip->operation, &neg, trip->op_b, nullptr, trip->type); 3377d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min)); 3387d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } 3397d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } 3407d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } 3417d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } 3427d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } 3437d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // General rule of linear induction a * i + b, for normalized 0 <= i < TC. 3447d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min), 3457d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik GetVal(info->op_b, trip, in_body, is_min)); 3467d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik} 3477d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik 348d14c59564870c910bdc823081f0ed1101f599231Aart BikInductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, 34922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInductionVarAnalysis::InductionInfo* trip, 3509401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik bool in_body, 3517d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const { 352d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes 353d14c59564870c910bdc823081f0ed1101f599231Aart Bik // more likely range analysis will compare the same instructions as terminal nodes. 35497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik int64_t value; 35597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value)) { 35697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return Value(static_cast<int32_t>(value)); 357d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (instruction->IsAdd()) { 35897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsIntAndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) { 35997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return AddValue(Value(static_cast<int32_t>(value)), 36097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik GetFetch(instruction->InputAt(1), trip, in_body, is_min)); 36197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } else if (IsIntAndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) { 36297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), 36397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik Value(static_cast<int32_t>(value))); 36422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik } 365b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik } else if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) { 366b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min); 3670d345cf8db01f40db250f80de5104e0df24234faAart Bik } else if (instruction->IsTypeConversion()) { 3680d345cf8db01f40db250f80de5104e0df24234faAart Bik // Since analysis is 32-bit (or narrower) we allow a widening along the path. 3690d345cf8db01f40db250f80de5104e0df24234faAart Bik if (instruction->AsTypeConversion()->GetInputType() == Primitive::kPrimInt && 3700d345cf8db01f40db250f80de5104e0df24234faAart Bik instruction->AsTypeConversion()->GetResultType() == Primitive::kPrimLong) { 3710d345cf8db01f40db250f80de5104e0df24234faAart Bik return GetFetch(instruction->InputAt(0), trip, in_body, is_min); 3720d345cf8db01f40db250f80de5104e0df24234faAart Bik } 373b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik } else if (is_min) { 3749401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // Special case for finding minimum: minimum of trip-count in loop-body is 1. 37522f058726d35dd8f40b3763649e61740b3d22535Aart Bik if (trip != nullptr && in_body && instruction == trip->op_a->fetch) { 37622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik return Value(1); 377d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 378d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 379d14c59564870c910bdc823081f0ed1101f599231Aart Bik return Value(instruction, 1, 0); 380d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 381d14c59564870c910bdc823081f0ed1101f599231Aart Bik 382cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart BikInductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info, 383cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik HInductionVarAnalysis::InductionInfo* trip, 3849401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik bool in_body, 3857d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const { 386d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (info != nullptr) { 387d14c59564870c910bdc823081f0ed1101f599231Aart Bik switch (info->induction_class) { 388d14c59564870c910bdc823081f0ed1101f599231Aart Bik case HInductionVarAnalysis::kInvariant: 389d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Invariants. 390d14c59564870c910bdc823081f0ed1101f599231Aart Bik switch (info->operation) { 391d14c59564870c910bdc823081f0ed1101f599231Aart Bik case HInductionVarAnalysis::kAdd: 3929401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return AddValue(GetVal(info->op_a, trip, in_body, is_min), 3939401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik GetVal(info->op_b, trip, in_body, is_min)); 394cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik case HInductionVarAnalysis::kSub: // second reversed! 3959401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return SubValue(GetVal(info->op_a, trip, in_body, is_min), 3969401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik GetVal(info->op_b, trip, in_body, !is_min)); 397cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik case HInductionVarAnalysis::kNeg: // second reversed! 398cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik return SubValue(Value(0), 3999401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik GetVal(info->op_b, trip, in_body, !is_min)); 400d14c59564870c910bdc823081f0ed1101f599231Aart Bik case HInductionVarAnalysis::kMul: 4019401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return GetMul(info->op_a, info->op_b, trip, in_body, is_min); 402d14c59564870c910bdc823081f0ed1101f599231Aart Bik case HInductionVarAnalysis::kDiv: 4039401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return GetDiv(info->op_a, info->op_b, trip, in_body, is_min); 404d14c59564870c910bdc823081f0ed1101f599231Aart Bik case HInductionVarAnalysis::kFetch: 4059401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return GetFetch(info->fetch, trip, in_body, is_min); 4069401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik case HInductionVarAnalysis::kTripCountInLoop: 407389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kTripCountInLoopUnsafe: 408aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (!in_body && !is_min) { // one extra! 40922f058726d35dd8f40b3763649e61740b3d22535Aart Bik return GetVal(info->op_a, trip, in_body, is_min); 4109401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik } 4119401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik FALLTHROUGH_INTENDED; 4129401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik case HInductionVarAnalysis::kTripCountInBody: 413389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kTripCountInBodyUnsafe: 414aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (is_min) { 415aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik return Value(0); 416aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } else if (in_body) { 41722f058726d35dd8f40b3763649e61740b3d22535Aart Bik return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1)); 4189401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik } 4199401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik break; 4209401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik default: 4219401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik break; 422d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 423d14c59564870c910bdc823081f0ed1101f599231Aart Bik break; 4247d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik case HInductionVarAnalysis::kLinear: { 4250d345cf8db01f40db250f80de5104e0df24234faAart Bik return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type); 4267d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } 427d14c59564870c910bdc823081f0ed1101f599231Aart Bik case HInductionVarAnalysis::kWrapAround: 428d14c59564870c910bdc823081f0ed1101f599231Aart Bik case HInductionVarAnalysis::kPeriodic: 4299401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return MergeVal(GetVal(info->op_a, trip, in_body, is_min), 4309401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik GetVal(info->op_b, trip, in_body, is_min), is_min); 431d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 432d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 433b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(); 434d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 435d14c59564870c910bdc823081f0ed1101f599231Aart Bik 436d14c59564870c910bdc823081f0ed1101f599231Aart BikInductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1, 437d14c59564870c910bdc823081f0ed1101f599231Aart Bik HInductionVarAnalysis::InductionInfo* info2, 438d14c59564870c910bdc823081f0ed1101f599231Aart Bik HInductionVarAnalysis::InductionInfo* trip, 4399401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik bool in_body, 4407d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const { 4419401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); 4429401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); 4439401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); 4449401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); 44597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Try to refine first operand. 44697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (!IsConstantValue(v1_min) && !IsConstantValue(v1_max)) { 44797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik RefineOuter(&v1_min, &v1_max); 44897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 44997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Constant times range. 45097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsSameConstantValue(v1_min, v1_max)) { 45197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return MulRangeAndConstant(v2_min, v2_max, v1_min, is_min); 45297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } else if (IsSameConstantValue(v2_min, v2_max)) { 45397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return MulRangeAndConstant(v1_min, v1_max, v2_min, is_min); 45497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 45597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Positive range vs. positive or negative range. 45697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { 45797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 45897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min ? MulValue(v1_min, v2_min) : MulValue(v1_max, v2_max); 45997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 46097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min ? MulValue(v1_max, v2_min) : MulValue(v1_min, v2_max); 461d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 46297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 46397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Negative range vs. positive or negative range. 46497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { 46597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 46697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min ? MulValue(v1_min, v2_max) : MulValue(v1_max, v2_min); 46797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 46897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min ? MulValue(v1_max, v2_max) : MulValue(v1_min, v2_min); 469d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 470d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 471b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(); 472d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 473d14c59564870c910bdc823081f0ed1101f599231Aart Bik 474d14c59564870c910bdc823081f0ed1101f599231Aart BikInductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1, 475d14c59564870c910bdc823081f0ed1101f599231Aart Bik HInductionVarAnalysis::InductionInfo* info2, 476d14c59564870c910bdc823081f0ed1101f599231Aart Bik HInductionVarAnalysis::InductionInfo* trip, 4779401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik bool in_body, 4787d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const { 4799401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); 4809401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); 4819401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); 4829401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); 48397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Range divided by constant. 48497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsSameConstantValue(v2_min, v2_max)) { 48597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return DivRangeAndConstant(v1_min, v1_max, v2_min, is_min); 48697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 48797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Positive range vs. positive or negative range. 48897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { 48997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 49097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min ? DivValue(v1_min, v2_max) : DivValue(v1_max, v2_min); 49197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 49297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min ? DivValue(v1_max, v2_max) : DivValue(v1_min, v2_min); 493d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 49497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 49597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Negative range vs. positive or negative range. 49697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { 49797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 49897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min ? DivValue(v1_min, v2_min) : DivValue(v1_max, v2_max); 49997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 50097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min ? DivValue(v1_max, v2_min) : DivValue(v1_min, v2_max); 501d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 502d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 503b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(); 504d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 505d14c59564870c910bdc823081f0ed1101f599231Aart Bik 50697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart BikInductionVarRange::Value InductionVarRange::MulRangeAndConstant(Value v_min, 50797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik Value v_max, 50897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik Value c, 50997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool is_min) const { 51097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min == (c.b_constant >= 0) ? MulValue(v_min, c) : MulValue(v_max, c); 51197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik} 51297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik 51397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart BikInductionVarRange::Value InductionVarRange::DivRangeAndConstant(Value v_min, 51497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik Value v_max, 51597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik Value c, 51697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool is_min) const { 51797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return is_min == (c.b_constant >= 0) ? DivValue(v_min, c) : DivValue(v_max, c); 5189401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik} 5199401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik 5207d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart BikInductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const { 521b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) { 522d14c59564870c910bdc823081f0ed1101f599231Aart Bik const int32_t b = v1.b_constant + v2.b_constant; 523d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (v1.a_constant == 0) { 524d14c59564870c910bdc823081f0ed1101f599231Aart Bik return Value(v2.instruction, v2.a_constant, b); 525d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (v2.a_constant == 0) { 526d14c59564870c910bdc823081f0ed1101f599231Aart Bik return Value(v1.instruction, v1.a_constant, b); 527d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (v1.instruction == v2.instruction && IsSafeAdd(v1.a_constant, v2.a_constant)) { 528d14c59564870c910bdc823081f0ed1101f599231Aart Bik return Value(v1.instruction, v1.a_constant + v2.a_constant, b); 529d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 530d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 531b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(); 532d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 533d14c59564870c910bdc823081f0ed1101f599231Aart Bik 5347d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart BikInductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) const { 535b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) { 536d14c59564870c910bdc823081f0ed1101f599231Aart Bik const int32_t b = v1.b_constant - v2.b_constant; 537d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) { 538d14c59564870c910bdc823081f0ed1101f599231Aart Bik return Value(v2.instruction, -v2.a_constant, b); 539d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (v2.a_constant == 0) { 540d14c59564870c910bdc823081f0ed1101f599231Aart Bik return Value(v1.instruction, v1.a_constant, b); 541d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (v1.instruction == v2.instruction && IsSafeSub(v1.a_constant, v2.a_constant)) { 542d14c59564870c910bdc823081f0ed1101f599231Aart Bik return Value(v1.instruction, v1.a_constant - v2.a_constant, b); 543d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 544d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 545b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(); 546d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 547d14c59564870c910bdc823081f0ed1101f599231Aart Bik 5487d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart BikInductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) const { 549b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik if (v1.is_known && v2.is_known) { 550b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik if (v1.a_constant == 0) { 551b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { 552b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant); 553b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik } 554b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik } else if (v2.a_constant == 0) { 555b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { 556b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant); 557b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik } 558d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 559d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 560b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(); 561d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 562d14c59564870c910bdc823081f0ed1101f599231Aart Bik 5637d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart BikInductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) const { 564b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik if (v1.is_known && v2.is_known && v1.a_constant == 0 && v2.a_constant == 0) { 565d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (IsSafeDiv(v1.b_constant, v2.b_constant)) { 566d14c59564870c910bdc823081f0ed1101f599231Aart Bik return Value(v1.b_constant / v2.b_constant); 567d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 568d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 569b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(); 570d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 571d14c59564870c910bdc823081f0ed1101f599231Aart Bik 5727d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart BikInductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) const { 573b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik if (v1.is_known && v2.is_known) { 574b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) { 575cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik return Value(v1.instruction, v1.a_constant, 576cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik is_min ? std::min(v1.b_constant, v2.b_constant) 577cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4Aart Bik : std::max(v1.b_constant, v2.b_constant)); 578b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik } 579d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 580b3365e0c4cda4f8f19284d2d418db158ab78d810Aart Bik return Value(); 581d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 582d14c59564870c910bdc823081f0ed1101f599231Aart Bik 5837d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart BikInductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) const { 58497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (v.instruction == nullptr) { 58597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return v; // nothing to refine 586b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik } 58797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HLoopInformation* loop = 58897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik v.instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop 58997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (loop == nullptr) { 59097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return v; // no loop 59197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 59297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, v.instruction); 59397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (info == nullptr) { 59497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return v; // no induction information 59597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 59697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Set up loop information. 59797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HBasicBlock* header = loop->GetHeader(); 59897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool in_body = true; // inner always in more outer 59997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HInductionVarAnalysis::InductionInfo* trip = 60097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); 60197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Try to refine "a x instruction + b" with outer loop range information on instruction. 60297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return AddValue(MulValue(Value(v.a_constant), GetVal(info, trip, in_body, is_min)), Value(v.b_constant)); 603b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik} 604b738d4f477a9b6f4c4f69153f9077f1559d2bca1Aart Bik 605aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bikbool InductionVarRange::GenerateCode(HInstruction* context, 606aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HInstruction* instruction, 607aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HGraph* graph, 608aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HBasicBlock* block, 609aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik /*out*/HInstruction** lower, 610aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik /*out*/HInstruction** upper, 611389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/HInstruction** taken_test, 612389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik /*out*/bool* needs_finite_test, 6137d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik /*out*/bool* needs_taken_test) const { 614aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop 61597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (loop == nullptr) { 61697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return false; // no loop 61797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 61897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction); 61997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (info == nullptr) { 62097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return false; // no induction information 62197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 62297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Set up loop information. 62397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HBasicBlock* header = loop->GetHeader(); 62497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik bool in_body = context->GetBlock() != header; 62597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik HInductionVarAnalysis::InductionInfo* trip = 62697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); 62797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (trip == nullptr) { 62897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return false; // codegen relies on trip count 62997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } 63097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Determine what tests are needed. A finite test is needed if the evaluation code uses the 63197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot" 63297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // the computed range). A taken test is needed for any unknown trip-count, even if evaluation 63397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // code does not use the trip-count explicitly (since there could be an implicit relation 63497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // between e.g. an invariant subscript and a not-taken condition). 63597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip); 63697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik *needs_taken_test = IsBodyTripCount(trip); 63797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Code generation for taken test: generate the code when requested or otherwise analyze 63897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // if code generation is feasible when taken test is needed. 63997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (taken_test != nullptr) { 64097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return GenerateCode(trip->op_b, nullptr, graph, block, taken_test, in_body, /* is_min */ false); 64197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik } else if (*needs_taken_test) { 64297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (!GenerateCode( 64397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min */ false)) { 64497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return false; 645389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 646aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 64797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Code generation for lower and upper. 64897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return 64997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Success on lower if invariant (not set), or code can be generated. 65097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik ((info->induction_class == HInductionVarAnalysis::kInvariant) || 65197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik GenerateCode(info, trip, graph, block, lower, in_body, /* is_min */ true)) && 65297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // And success on upper. 65397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false); 654aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik} 655aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik 656aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bikbool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, 657aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HInductionVarAnalysis::InductionInfo* trip, 658aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HGraph* graph, // when set, code is generated 659aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HBasicBlock* block, 660aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik /*out*/HInstruction** result, 661aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik bool in_body, 6627d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik bool is_min) const { 663aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (info != nullptr) { 6640d345cf8db01f40db250f80de5104e0df24234faAart Bik // Verify type safety. 665aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik Primitive::Type type = Primitive::kPrimInt; 6660d345cf8db01f40db250f80de5104e0df24234faAart Bik if (info->type != type) { 6670d345cf8db01f40db250f80de5104e0df24234faAart Bik return false; 6680d345cf8db01f40db250f80de5104e0df24234faAart Bik } 6690d345cf8db01f40db250f80de5104e0df24234faAart Bik // Handle current operation. 670aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HInstruction* opa = nullptr; 671aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HInstruction* opb = nullptr; 672aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik switch (info->induction_class) { 673aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik case HInductionVarAnalysis::kInvariant: 674aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik // Invariants. 675aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik switch (info->operation) { 676aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik case HInductionVarAnalysis::kAdd: 677389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kLT: 678389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kLE: 679389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kGT: 680389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kGE: 681aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) && 682aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { 683aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (graph != nullptr) { 684389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik HInstruction* operation = nullptr; 685389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik switch (info->operation) { 686389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kAdd: 687389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik operation = new (graph->GetArena()) HAdd(type, opa, opb); break; 688389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kLT: 689389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik operation = new (graph->GetArena()) HLessThan(opa, opb); break; 690389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kLE: 691389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik operation = new (graph->GetArena()) HLessThanOrEqual(opa, opb); break; 692389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kGT: 693389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik operation = new (graph->GetArena()) HGreaterThan(opa, opb); break; 694389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kGE: 695389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik operation = new (graph->GetArena()) HGreaterThanOrEqual(opa, opb); break; 696389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik default: 697389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik LOG(FATAL) << "unknown operation"; 698389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 699389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik *result = Insert(block, operation); 700aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 701aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik return true; 702aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 703aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik break; 704aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik case HInductionVarAnalysis::kSub: // second reversed! 705aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) && 706aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) { 707aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (graph != nullptr) { 708aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik *result = Insert(block, new (graph->GetArena()) HSub(type, opa, opb)); 709aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 710aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik return true; 711aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 712aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik break; 713aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik case HInductionVarAnalysis::kNeg: // reversed! 714aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) { 715aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (graph != nullptr) { 716aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik *result = Insert(block, new (graph->GetArena()) HNeg(type, opb)); 717aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 718aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik return true; 719aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 720aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik break; 721aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik case HInductionVarAnalysis::kFetch: 7220d345cf8db01f40db250f80de5104e0df24234faAart Bik if (graph != nullptr) { 7230d345cf8db01f40db250f80de5104e0df24234faAart Bik *result = info->fetch; // already in HIR 724aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 7250d345cf8db01f40db250f80de5104e0df24234faAart Bik return true; 726aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik case HInductionVarAnalysis::kTripCountInLoop: 727389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kTripCountInLoopUnsafe: 728aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (!in_body && !is_min) { // one extra! 72922f058726d35dd8f40b3763649e61740b3d22535Aart Bik return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min); 730aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 731aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik FALLTHROUGH_INTENDED; 732aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik case HInductionVarAnalysis::kTripCountInBody: 733389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kTripCountInBodyUnsafe: 734aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (is_min) { 735aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (graph != nullptr) { 736aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik *result = graph->GetIntConstant(0); 737aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 738aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik return true; 739aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } else if (in_body) { 74022f058726d35dd8f40b3763649e61740b3d22535Aart Bik if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) { 741aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik if (graph != nullptr) { 742aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik *result = Insert(block, 743aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik new (graph->GetArena()) 744aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik HSub(type, opb, graph->GetIntConstant(1))); 745aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 746aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik return true; 747aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 748aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 749aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik break; 750aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik default: 751aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik break; 752aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 753aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik break; 754389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik case HInductionVarAnalysis::kLinear: { 7554a34277c55279ba57ab361f7580db846a201d9b1Aart Bik // Linear induction a * i + b, for normalized 0 <= i < TC. Restrict to unit stride only 7564a34277c55279ba57ab361f7580db846a201d9b1Aart Bik // to avoid arithmetic wrap-around situations that are hard to guard against. 75797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik int64_t stride_value = 0; 75897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstant(info->op_a, kExact, &stride_value)) { 7594a34277c55279ba57ab361f7580db846a201d9b1Aart Bik if (stride_value == 1 || stride_value == -1) { 7604a34277c55279ba57ab361f7580db846a201d9b1Aart Bik const bool is_min_a = stride_value == 1 ? is_min : !is_min; 7614a34277c55279ba57ab361f7580db846a201d9b1Aart Bik if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) && 7624a34277c55279ba57ab361f7580db846a201d9b1Aart Bik GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { 7634a34277c55279ba57ab361f7580db846a201d9b1Aart Bik if (graph != nullptr) { 7644a34277c55279ba57ab361f7580db846a201d9b1Aart Bik HInstruction* oper; 7654a34277c55279ba57ab361f7580db846a201d9b1Aart Bik if (stride_value == 1) { 7664a34277c55279ba57ab361f7580db846a201d9b1Aart Bik oper = new (graph->GetArena()) HAdd(type, opa, opb); 7674a34277c55279ba57ab361f7580db846a201d9b1Aart Bik } else { 7684a34277c55279ba57ab361f7580db846a201d9b1Aart Bik oper = new (graph->GetArena()) HSub(type, opb, opa); 769389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik } 7704a34277c55279ba57ab361f7580db846a201d9b1Aart Bik *result = Insert(block, oper); 771aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 7724a34277c55279ba57ab361f7580db846a201d9b1Aart Bik return true; 773aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 774aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 775aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 776aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik break; 7774a34277c55279ba57ab361f7580db846a201d9b1Aart Bik } 7784a34277c55279ba57ab361f7580db846a201d9b1Aart Bik case HInductionVarAnalysis::kWrapAround: 7794a34277c55279ba57ab361f7580db846a201d9b1Aart Bik case HInductionVarAnalysis::kPeriodic: { 7804a34277c55279ba57ab361f7580db846a201d9b1Aart Bik // Wrap-around and periodic inductions are restricted to constants only, so that extreme 7814a34277c55279ba57ab361f7580db846a201d9b1Aart Bik // values are easy to test at runtime without complications of arithmetic wrap-around. 7824a34277c55279ba57ab361f7580db846a201d9b1Aart Bik Value extreme = GetVal(info, trip, in_body, is_min); 78397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsConstantValue(extreme)) { 7844a34277c55279ba57ab361f7580db846a201d9b1Aart Bik if (graph != nullptr) { 7854a34277c55279ba57ab361f7580db846a201d9b1Aart Bik *result = graph->GetIntConstant(extreme.b_constant); 7864a34277c55279ba57ab361f7580db846a201d9b1Aart Bik } 7874a34277c55279ba57ab361f7580db846a201d9b1Aart Bik return true; 7884a34277c55279ba57ab361f7580db846a201d9b1Aart Bik } 7894a34277c55279ba57ab361f7580db846a201d9b1Aart Bik break; 7904a34277c55279ba57ab361f7580db846a201d9b1Aart Bik } 791389b3dbf5c5390056ff4dacac464219853dd3cdaAart Bik default: 792aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik break; 793aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 794aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik } 795aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik return false; 796aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik} 797aec3cce52009afe436a6db0280d6d5aee9b8d4d4Aart Bik 798d14c59564870c910bdc823081f0ed1101f599231Aart Bik} // namespace art 799