Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2015 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 17 | #include "induction_var_range.h" |
| 18 | |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 19 | #include <limits> |
| 20 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 21 | namespace art { |
| 22 | |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 23 | /** Returns true if 64-bit constant fits in 32-bit constant. */ |
| 24 | static bool CanLongValueFitIntoInt(int64_t c) { |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 25 | return std::numeric_limits<int32_t>::min() <= c && c <= std::numeric_limits<int32_t>::max(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 26 | } |
| 27 | |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 28 | /** Returns true if 32-bit addition can be done safely. */ |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 29 | static bool IsSafeAdd(int32_t c1, int32_t c2) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 30 | return CanLongValueFitIntoInt(static_cast<int64_t>(c1) + static_cast<int64_t>(c2)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 31 | } |
| 32 | |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 33 | /** Returns true if 32-bit subtraction can be done safely. */ |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 34 | static bool IsSafeSub(int32_t c1, int32_t c2) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 35 | return CanLongValueFitIntoInt(static_cast<int64_t>(c1) - static_cast<int64_t>(c2)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 36 | } |
| 37 | |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 38 | /** Returns true if 32-bit multiplication can be done safely. */ |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 39 | static bool IsSafeMul(int32_t c1, int32_t c2) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 40 | return CanLongValueFitIntoInt(static_cast<int64_t>(c1) * static_cast<int64_t>(c2)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 41 | } |
| 42 | |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 43 | /** Returns true if 32-bit division can be done safely. */ |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 44 | static bool IsSafeDiv(int32_t c1, int32_t c2) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 45 | return c2 != 0 && CanLongValueFitIntoInt(static_cast<int64_t>(c1) / static_cast<int64_t>(c2)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 46 | } |
| 47 | |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 48 | /** Returns true for 32/64-bit constant instruction. */ |
| 49 | static bool IsIntAndGet(HInstruction* instruction, int64_t* value) { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 50 | if (instruction->IsIntConstant()) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 51 | *value = instruction->AsIntConstant()->GetValue(); |
| 52 | return true; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 53 | } else if (instruction->IsLongConstant()) { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 54 | *value = instruction->AsLongConstant()->GetValue(); |
| 55 | return true; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 56 | } |
| 57 | return false; |
| 58 | } |
| 59 | |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 60 | /** |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 61 | * Detects an instruction that is >= 0. As long as the value is carried by |
| 62 | * a single instruction, arithmetic wrap-around cannot occur. |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 63 | */ |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 64 | static bool IsGEZero(HInstruction* instruction) { |
| 65 | DCHECK(instruction != nullptr); |
| 66 | if (instruction->IsArrayLength()) { |
| 67 | return true; |
| 68 | } else if (instruction->IsInvokeStaticOrDirect()) { |
| 69 | switch (instruction->AsInvoke()->GetIntrinsic()) { |
| 70 | case Intrinsics::kMathMinIntInt: |
| 71 | case Intrinsics::kMathMinLongLong: |
| 72 | // Instruction MIN(>=0, >=0) is >= 0. |
| 73 | return IsGEZero(instruction->InputAt(0)) && |
| 74 | IsGEZero(instruction->InputAt(1)); |
| 75 | case Intrinsics::kMathAbsInt: |
| 76 | case Intrinsics::kMathAbsLong: |
| 77 | // Instruction ABS(x) is >= 0. |
| 78 | return true; |
| 79 | default: |
| 80 | break; |
| 81 | } |
| 82 | } |
| 83 | int64_t value = -1; |
| 84 | return IsIntAndGet(instruction, &value) && value >= 0; |
| 85 | } |
| 86 | |
| 87 | /** Hunts "under the hood" for a suitable instruction at the hint. */ |
| 88 | static bool IsMaxAtHint( |
| 89 | HInstruction* instruction, HInstruction* hint, /*out*/HInstruction** suitable) { |
| 90 | if (instruction->IsInvokeStaticOrDirect()) { |
| 91 | switch (instruction->AsInvoke()->GetIntrinsic()) { |
| 92 | case Intrinsics::kMathMinIntInt: |
| 93 | case Intrinsics::kMathMinLongLong: |
| 94 | // For MIN(x, y), return most suitable x or y as maximum. |
| 95 | return IsMaxAtHint(instruction->InputAt(0), hint, suitable) || |
| 96 | IsMaxAtHint(instruction->InputAt(1), hint, suitable); |
| 97 | default: |
| 98 | break; |
| 99 | } |
| 100 | } else { |
| 101 | *suitable = instruction; |
| 102 | while (instruction->IsArrayLength() || |
| 103 | instruction->IsNullCheck() || |
| 104 | instruction->IsNewArray()) { |
| 105 | instruction = instruction->InputAt(0); |
| 106 | } |
| 107 | return instruction == hint; |
| 108 | } |
| 109 | return false; |
| 110 | } |
| 111 | |
| 112 | /** Post-analysis simplification of a minimum value that makes the bound more useful to clients. */ |
| 113 | static InductionVarRange::Value SimplifyMin(InductionVarRange::Value v) { |
| 114 | if (v.is_known && v.a_constant == 1 && v.b_constant <= 0) { |
| 115 | // If a == 1, instruction >= 0 and b <= 0, just return the constant b. |
| 116 | // No arithmetic wrap-around can occur. |
| 117 | if (IsGEZero(v.instruction)) { |
| 118 | return InductionVarRange::Value(v.b_constant); |
| 119 | } |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 120 | } |
| 121 | return v; |
| 122 | } |
| 123 | |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 124 | /** Post-analysis simplification of a maximum value that makes the bound more useful to clients. */ |
| 125 | static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v, HInstruction* hint) { |
| 126 | if (v.is_known && v.a_constant >= 1) { |
| 127 | // An upper bound a * (length / a) + b, where a >= 1, can be conservatively rewritten as |
| 128 | // length + b because length >= 0 is true. |
| 129 | int64_t value; |
| 130 | if (v.instruction->IsDiv() && |
| 131 | v.instruction->InputAt(0)->IsArrayLength() && |
| 132 | IsIntAndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) { |
| 133 | return InductionVarRange::Value(v.instruction->InputAt(0), 1, v.b_constant); |
| 134 | } |
| 135 | // If a == 1, the most suitable one suffices as maximum value. |
| 136 | HInstruction* suitable = nullptr; |
| 137 | if (v.a_constant == 1 && IsMaxAtHint(v.instruction, hint, &suitable)) { |
| 138 | return InductionVarRange::Value(suitable, 1, v.b_constant); |
| 139 | } |
| 140 | } |
| 141 | return v; |
| 142 | } |
| 143 | |
| 144 | /** Tests for a constant value. */ |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 145 | static bool IsConstantValue(InductionVarRange::Value v) { |
| 146 | return v.is_known && v.a_constant == 0; |
| 147 | } |
| 148 | |
| 149 | /** Corrects a value for type to account for arithmetic wrap-around in lower precision. */ |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 150 | static InductionVarRange::Value CorrectForType(InductionVarRange::Value v, Primitive::Type type) { |
| 151 | switch (type) { |
| 152 | case Primitive::kPrimShort: |
| 153 | case Primitive::kPrimChar: |
| 154 | case Primitive::kPrimByte: { |
| 155 | // Constants within range only. |
| 156 | // TODO: maybe some room for improvement, like allowing widening conversions |
| 157 | const int32_t min = Primitive::MinValueOfIntegralType(type); |
| 158 | const int32_t max = Primitive::MaxValueOfIntegralType(type); |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 159 | return (IsConstantValue(v) && min <= v.b_constant && v.b_constant <= max) |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 160 | ? v |
| 161 | : InductionVarRange::Value(); |
| 162 | } |
| 163 | default: |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 164 | return v; |
| 165 | } |
| 166 | } |
| 167 | |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 168 | /** Inserts an instruction. */ |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 169 | static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { |
| 170 | DCHECK(block != nullptr); |
| 171 | DCHECK(block->GetLastInstruction() != nullptr) << block->GetBlockId(); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 172 | DCHECK(instruction != nullptr); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 173 | block->InsertInstructionBefore(instruction, block->GetLastInstruction()); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 174 | return instruction; |
| 175 | } |
| 176 | |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 177 | /** Obtains loop's control instruction. */ |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 178 | static HInstruction* GetLoopControl(HLoopInformation* loop) { |
| 179 | DCHECK(loop != nullptr); |
| 180 | return loop->GetHeader()->GetLastInstruction(); |
| 181 | } |
| 182 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 183 | // |
| 184 | // Public class methods. |
| 185 | // |
| 186 | |
| 187 | InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis) |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 188 | : induction_analysis_(induction_analysis), |
| 189 | chase_hint_(nullptr) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 190 | DCHECK(induction_analysis != nullptr); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 191 | } |
| 192 | |
Aart Bik | 1fc3afb | 2016-02-02 13:26:16 -0800 | [diff] [blame] | 193 | bool InductionVarRange::GetInductionRange(HInstruction* context, |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 194 | HInstruction* instruction, |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 195 | HInstruction* chase_hint, |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 196 | /*out*/Value* min_val, |
| 197 | /*out*/Value* max_val, |
| 198 | /*out*/bool* needs_finite_test) { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 199 | HLoopInformation* loop = nullptr; |
| 200 | HInductionVarAnalysis::InductionInfo* info = nullptr; |
| 201 | HInductionVarAnalysis::InductionInfo* trip = nullptr; |
| 202 | if (!HasInductionInfo(context, instruction, &loop, &info, &trip)) { |
| 203 | return false; |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 204 | } |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 205 | // Type int or lower (this is not too restrictive since intended clients, like |
| 206 | // bounds check elimination, will have truncated higher precision induction |
| 207 | // at their use point already). |
| 208 | switch (info->type) { |
| 209 | case Primitive::kPrimInt: |
| 210 | case Primitive::kPrimShort: |
| 211 | case Primitive::kPrimChar: |
| 212 | case Primitive::kPrimByte: |
| 213 | break; |
| 214 | default: |
| 215 | return false; |
| 216 | } |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 217 | // Find range. |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 218 | chase_hint_ = chase_hint; |
| 219 | bool in_body = context->GetBlock() != loop->GetHeader(); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 220 | int64_t stride_value = 0; |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 221 | *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min */ true)); |
| 222 | *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false), chase_hint); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 223 | *needs_finite_test = NeedsTripCount(info, &stride_value) && IsUnsafeTripCount(trip); |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 224 | chase_hint_ = nullptr; |
| 225 | // Retry chasing constants for wrap-around (merge sensitive). |
| 226 | if (!min_val->is_known && info->induction_class == HInductionVarAnalysis::kWrapAround) { |
| 227 | *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min */ true)); |
| 228 | } |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 229 | return true; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 230 | } |
| 231 | |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 232 | bool InductionVarRange::CanGenerateRange(HInstruction* context, |
| 233 | HInstruction* instruction, |
| 234 | /*out*/bool* needs_finite_test, |
| 235 | /*out*/bool* needs_taken_test) { |
| 236 | bool is_last_value = false; |
| 237 | int64_t stride_value = 0; |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 238 | return GenerateRangeOrLastValue(context, |
| 239 | instruction, |
| 240 | is_last_value, |
| 241 | nullptr, |
| 242 | nullptr, |
| 243 | nullptr, |
| 244 | nullptr, |
| 245 | nullptr, // nothing generated yet |
| 246 | &stride_value, |
| 247 | needs_finite_test, |
| 248 | needs_taken_test) |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 249 | && (stride_value == -1 || |
| 250 | stride_value == 0 || |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 251 | stride_value == 1); // avoid arithmetic wrap-around anomalies. |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 252 | } |
| 253 | |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 254 | void InductionVarRange::GenerateRange(HInstruction* context, |
| 255 | HInstruction* instruction, |
| 256 | HGraph* graph, |
| 257 | HBasicBlock* block, |
| 258 | /*out*/HInstruction** lower, |
| 259 | /*out*/HInstruction** upper) { |
| 260 | bool is_last_value = false; |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 261 | int64_t stride_value = 0; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 262 | bool b1, b2; // unused |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 263 | if (!GenerateRangeOrLastValue(context, |
| 264 | instruction, |
| 265 | is_last_value, |
| 266 | graph, |
| 267 | block, |
| 268 | lower, |
| 269 | upper, |
| 270 | nullptr, |
| 271 | &stride_value, |
| 272 | &b1, |
| 273 | &b2)) { |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 274 | LOG(FATAL) << "Failed precondition: CanGenerateRange()"; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 275 | } |
| 276 | } |
| 277 | |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 278 | HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context, |
| 279 | HGraph* graph, |
| 280 | HBasicBlock* block) { |
| 281 | HInstruction* taken_test = nullptr; |
| 282 | bool is_last_value = false; |
| 283 | int64_t stride_value = 0; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 284 | bool b1, b2; // unused |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 285 | if (!GenerateRangeOrLastValue(context, |
| 286 | context, |
| 287 | is_last_value, |
| 288 | graph, |
| 289 | block, |
| 290 | nullptr, |
| 291 | nullptr, |
| 292 | &taken_test, |
| 293 | &stride_value, |
| 294 | &b1, |
| 295 | &b2)) { |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 296 | LOG(FATAL) << "Failed precondition: CanGenerateRange()"; |
| 297 | } |
| 298 | return taken_test; |
| 299 | } |
| 300 | |
| 301 | bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) { |
| 302 | bool is_last_value = true; |
| 303 | int64_t stride_value = 0; |
| 304 | bool needs_finite_test = false; |
| 305 | bool needs_taken_test = false; |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 306 | return GenerateRangeOrLastValue(instruction, |
| 307 | instruction, |
| 308 | is_last_value, |
| 309 | nullptr, |
| 310 | nullptr, |
| 311 | nullptr, |
| 312 | nullptr, |
| 313 | nullptr, // nothing generated yet |
| 314 | &stride_value, |
| 315 | &needs_finite_test, |
| 316 | &needs_taken_test) |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 317 | && !needs_finite_test && !needs_taken_test; |
| 318 | } |
| 319 | |
| 320 | HInstruction* InductionVarRange::GenerateLastValue(HInstruction* instruction, |
| 321 | HGraph* graph, |
| 322 | HBasicBlock* block) { |
| 323 | HInstruction* last_value = nullptr; |
| 324 | bool is_last_value = true; |
| 325 | int64_t stride_value = 0; |
| 326 | bool b1, b2; // unused |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 327 | if (!GenerateRangeOrLastValue(instruction, |
| 328 | instruction, |
| 329 | is_last_value, |
| 330 | graph, |
| 331 | block, |
| 332 | &last_value, |
| 333 | &last_value, |
| 334 | nullptr, |
| 335 | &stride_value, |
| 336 | &b1, |
| 337 | &b2)) { |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 338 | LOG(FATAL) << "Failed precondition: CanGenerateLastValue()"; |
| 339 | } |
| 340 | return last_value; |
| 341 | } |
| 342 | |
| 343 | void InductionVarRange::Replace(HInstruction* instruction, |
| 344 | HInstruction* fetch, |
| 345 | HInstruction* replacement) { |
| 346 | for (HLoopInformation* lp = instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop |
| 347 | lp != nullptr; |
| 348 | lp = lp->GetPreHeader()->GetLoopInformation()) { |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 349 | // Update instruction's information. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 350 | ReplaceInduction(induction_analysis_->LookupInfo(lp, instruction), fetch, replacement); |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 351 | // Update loop's trip-count information. |
| 352 | ReplaceInduction(induction_analysis_->LookupInfo(lp, GetLoopControl(lp)), fetch, replacement); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 353 | } |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 354 | } |
| 355 | |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 356 | bool InductionVarRange::IsFinite(HLoopInformation* loop) const { |
| 357 | HInductionVarAnalysis::InductionInfo *trip = |
| 358 | induction_analysis_->LookupInfo(loop, GetLoopControl(loop)); |
| 359 | return trip != nullptr && !IsUnsafeTripCount(trip); |
| 360 | } |
| 361 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 362 | // |
| 363 | // Private class methods. |
| 364 | // |
| 365 | |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 366 | bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, |
| 367 | ConstantRequest request, |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 368 | /*out*/ int64_t* value) const { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 369 | if (info != nullptr) { |
| 370 | // A direct 32-bit or 64-bit constant fetch. This immediately satisfies |
| 371 | // any of the three requests (kExact, kAtMost, and KAtLeast). |
| 372 | if (info->induction_class == HInductionVarAnalysis::kInvariant && |
| 373 | info->operation == HInductionVarAnalysis::kFetch) { |
| 374 | if (IsIntAndGet(info->fetch, value)) { |
| 375 | return true; |
| 376 | } |
| 377 | } |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 378 | // Try range analysis on the invariant, only accept a proper range |
| 379 | // to avoid arithmetic wrap-around anomalies. |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 380 | Value min_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ true); |
| 381 | Value max_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ false); |
| 382 | if (IsConstantValue(min_val) && |
| 383 | IsConstantValue(max_val) && min_val.b_constant <= max_val.b_constant) { |
| 384 | if ((request == kExact && min_val.b_constant == max_val.b_constant) || request == kAtMost) { |
| 385 | *value = max_val.b_constant; |
| 386 | return true; |
| 387 | } else if (request == kAtLeast) { |
| 388 | *value = min_val.b_constant; |
Aart Bik | 358af83 | 2016-02-24 14:17:53 -0800 | [diff] [blame] | 389 | return true; |
| 390 | } |
| 391 | } |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 392 | } |
| 393 | return false; |
| 394 | } |
| 395 | |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 396 | bool InductionVarRange::HasInductionInfo( |
| 397 | HInstruction* context, |
| 398 | HInstruction* instruction, |
| 399 | /*out*/ HLoopInformation** loop, |
| 400 | /*out*/ HInductionVarAnalysis::InductionInfo** info, |
| 401 | /*out*/ HInductionVarAnalysis::InductionInfo** trip) const { |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 402 | HLoopInformation* lp = context->GetBlock()->GetLoopInformation(); // closest enveloping loop |
| 403 | if (lp != nullptr) { |
| 404 | HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(lp, instruction); |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 405 | if (i != nullptr) { |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 406 | *loop = lp; |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 407 | *info = i; |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 408 | *trip = induction_analysis_->LookupInfo(lp, GetLoopControl(lp)); |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 409 | return true; |
| 410 | } |
| 411 | } |
| 412 | return false; |
| 413 | } |
| 414 | |
| 415 | bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const { |
| 416 | if (trip != nullptr) { |
| 417 | // Both bounds that define a trip-count are well-behaved if they either are not defined |
| 418 | // in any loop, or are contained in a proper interval. This allows finding the min/max |
| 419 | // of an expression by chasing outward. |
| 420 | InductionVarRange range(induction_analysis_); |
| 421 | HInductionVarAnalysis::InductionInfo* lower = trip->op_b->op_a; |
| 422 | HInductionVarAnalysis::InductionInfo* upper = trip->op_b->op_b; |
| 423 | int64_t not_used = 0; |
| 424 | return (!HasFetchInLoop(lower) || range.IsConstant(lower, kAtLeast, ¬_used)) && |
| 425 | (!HasFetchInLoop(upper) || range.IsConstant(upper, kAtLeast, ¬_used)); |
| 426 | } |
| 427 | return true; |
| 428 | } |
| 429 | |
| 430 | bool InductionVarRange::HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const { |
| 431 | if (info != nullptr) { |
| 432 | if (info->induction_class == HInductionVarAnalysis::kInvariant && |
| 433 | info->operation == HInductionVarAnalysis::kFetch) { |
| 434 | return info->fetch->GetBlock()->GetLoopInformation() != nullptr; |
| 435 | } |
| 436 | return HasFetchInLoop(info->op_a) || HasFetchInLoop(info->op_b); |
| 437 | } |
| 438 | return false; |
| 439 | } |
| 440 | |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 441 | bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info, |
| 442 | int64_t* stride_value) const { |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 443 | if (info != nullptr) { |
| 444 | if (info->induction_class == HInductionVarAnalysis::kLinear) { |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 445 | return IsConstant(info->op_a, kExact, stride_value); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 446 | } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) { |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 447 | return NeedsTripCount(info->op_b, stride_value); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 448 | } |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 449 | } |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 450 | return false; |
| 451 | } |
| 452 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 453 | bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const { |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 454 | if (trip != nullptr) { |
| 455 | if (trip->induction_class == HInductionVarAnalysis::kInvariant) { |
| 456 | return trip->operation == HInductionVarAnalysis::kTripCountInBody || |
| 457 | trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe; |
| 458 | } |
| 459 | } |
| 460 | return false; |
| 461 | } |
| 462 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 463 | bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const { |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 464 | if (trip != nullptr) { |
| 465 | if (trip->induction_class == HInductionVarAnalysis::kInvariant) { |
| 466 | return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe || |
| 467 | trip->operation == HInductionVarAnalysis::kTripCountInLoopUnsafe; |
| 468 | } |
| 469 | } |
| 470 | return false; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 471 | } |
| 472 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 473 | InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info, |
| 474 | HInductionVarAnalysis::InductionInfo* trip, |
| 475 | bool in_body, |
| 476 | bool is_min) const { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 477 | // Detect common situation where an offset inside the trip-count cancels out during range |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 478 | // analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding |
| 479 | // min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information |
| 480 | // with intermediate results that only incorporate single instructions. |
| 481 | if (trip != nullptr) { |
| 482 | HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a; |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 483 | if (trip_expr->type == info->type && trip_expr->operation == HInductionVarAnalysis::kSub) { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 484 | int64_t stride_value = 0; |
| 485 | if (IsConstant(info->op_a, kExact, &stride_value)) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 486 | if (!is_min && stride_value == 1) { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 487 | // Test original trip's negative operand (trip_expr->op_b) against offset of induction. |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 488 | if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) { |
| 489 | // Analyze cancelled trip with just the positive operand (trip_expr->op_a). |
| 490 | HInductionVarAnalysis::InductionInfo cancelled_trip( |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 491 | trip->induction_class, |
| 492 | trip->operation, |
| 493 | trip_expr->op_a, |
| 494 | trip->op_b, |
| 495 | nullptr, |
| 496 | trip->type); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 497 | return GetVal(&cancelled_trip, trip, in_body, is_min); |
| 498 | } |
| 499 | } else if (is_min && stride_value == -1) { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 500 | // Test original trip's positive operand (trip_expr->op_a) against offset of induction. |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 501 | if (HInductionVarAnalysis::InductionEqual(trip_expr->op_a, info->op_b)) { |
| 502 | // Analyze cancelled trip with just the negative operand (trip_expr->op_b). |
| 503 | HInductionVarAnalysis::InductionInfo neg( |
| 504 | HInductionVarAnalysis::kInvariant, |
| 505 | HInductionVarAnalysis::kNeg, |
| 506 | nullptr, |
| 507 | trip_expr->op_b, |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 508 | nullptr, |
| 509 | trip->type); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 510 | HInductionVarAnalysis::InductionInfo cancelled_trip( |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 511 | trip->induction_class, trip->operation, &neg, trip->op_b, nullptr, trip->type); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 512 | return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min)); |
| 513 | } |
| 514 | } |
| 515 | } |
| 516 | } |
| 517 | } |
| 518 | // General rule of linear induction a * i + b, for normalized 0 <= i < TC. |
| 519 | return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min), |
| 520 | GetVal(info->op_b, trip, in_body, is_min)); |
| 521 | } |
| 522 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 523 | InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 524 | HInductionVarAnalysis::InductionInfo* trip, |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 525 | bool in_body, |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 526 | bool is_min) const { |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 527 | // Special case when chasing constants: single instruction that denotes trip count in the |
| 528 | // loop-body is minimal 1 and maximal, with safe trip-count, max int, |
| 529 | if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 530 | if (is_min) { |
| 531 | return Value(1); |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 532 | } else if (!IsUnsafeTripCount(trip)) { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 533 | return Value(std::numeric_limits<int32_t>::max()); |
| 534 | } |
| 535 | } |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 536 | // Unless at a constant or hint, chase the instruction a bit deeper into the HIR tree, so that |
| 537 | // it becomes more likely range analysis will compare the same instructions as terminal nodes. |
| 538 | int64_t value; |
| 539 | if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value)) { |
| 540 | // Proper constant reveals best information. |
| 541 | return Value(static_cast<int32_t>(value)); |
| 542 | } else if (instruction == chase_hint_) { |
| 543 | // At hint, fetch is represented by itself. |
| 544 | return Value(instruction, 1, 0); |
| 545 | } else if (instruction->IsAdd()) { |
| 546 | // Incorporate suitable constants in the chased value. |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 547 | if (IsIntAndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) { |
| 548 | return AddValue(Value(static_cast<int32_t>(value)), |
| 549 | GetFetch(instruction->InputAt(1), trip, in_body, is_min)); |
| 550 | } else if (IsIntAndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) { |
| 551 | return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), |
| 552 | Value(static_cast<int32_t>(value))); |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 553 | } |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 554 | } else if (instruction->IsArrayLength()) { |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 555 | // Exploit length properties when chasing constants or chase into a new array declaration. |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 556 | if (chase_hint_ == nullptr) { |
| 557 | return is_min ? Value(0) : Value(std::numeric_limits<int32_t>::max()); |
| 558 | } else if (instruction->InputAt(0)->IsNewArray()) { |
| 559 | return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min); |
| 560 | } |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 561 | } else if (instruction->IsTypeConversion()) { |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 562 | // Since analysis is 32-bit (or narrower), chase beyond widening along the path. |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 563 | if (instruction->AsTypeConversion()->GetInputType() == Primitive::kPrimInt && |
| 564 | instruction->AsTypeConversion()->GetResultType() == Primitive::kPrimLong) { |
| 565 | return GetFetch(instruction->InputAt(0), trip, in_body, is_min); |
| 566 | } |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 567 | } |
| 568 | // Chase an invariant fetch that is defined by an outer loop if the trip-count used |
| 569 | // so far is well-behaved in both bounds and the next trip-count is safe. |
| 570 | // Example: |
| 571 | // for (int i = 0; i <= 100; i++) // safe |
| 572 | // for (int j = 0; j <= i; j++) // well-behaved |
| 573 | // j is in range [0, i ] (if i is chase hint) |
| 574 | // or in range [0, 100] (otherwise) |
| 575 | HLoopInformation* next_loop = nullptr; |
| 576 | HInductionVarAnalysis::InductionInfo* next_info = nullptr; |
| 577 | HInductionVarAnalysis::InductionInfo* next_trip = nullptr; |
| 578 | bool next_in_body = true; // inner loop is always in body of outer loop |
| 579 | if (HasInductionInfo(instruction, instruction, &next_loop, &next_info, &next_trip) && |
| 580 | IsWellBehavedTripCount(trip) && |
| 581 | !IsUnsafeTripCount(next_trip)) { |
| 582 | return GetVal(next_info, next_trip, next_in_body, is_min); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 583 | } |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 584 | // Fetch is represented by itself. |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 585 | return Value(instruction, 1, 0); |
| 586 | } |
| 587 | |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 588 | InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info, |
| 589 | HInductionVarAnalysis::InductionInfo* trip, |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 590 | bool in_body, |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 591 | bool is_min) const { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 592 | if (info != nullptr) { |
| 593 | switch (info->induction_class) { |
| 594 | case HInductionVarAnalysis::kInvariant: |
| 595 | // Invariants. |
| 596 | switch (info->operation) { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 597 | case HInductionVarAnalysis::kAdd: |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 598 | return AddValue(GetVal(info->op_a, trip, in_body, is_min), |
| 599 | GetVal(info->op_b, trip, in_body, is_min)); |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 600 | case HInductionVarAnalysis::kSub: // second reversed! |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 601 | return SubValue(GetVal(info->op_a, trip, in_body, is_min), |
| 602 | GetVal(info->op_b, trip, in_body, !is_min)); |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 603 | case HInductionVarAnalysis::kNeg: // second reversed! |
| 604 | return SubValue(Value(0), |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 605 | GetVal(info->op_b, trip, in_body, !is_min)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 606 | case HInductionVarAnalysis::kMul: |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 607 | return GetMul(info->op_a, info->op_b, trip, in_body, is_min); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 608 | case HInductionVarAnalysis::kDiv: |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 609 | return GetDiv(info->op_a, info->op_b, trip, in_body, is_min); |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 610 | case HInductionVarAnalysis::kXor: |
| 611 | return GetXor(info->op_a, info->op_b); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 612 | case HInductionVarAnalysis::kFetch: |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 613 | return GetFetch(info->fetch, trip, in_body, is_min); |
| 614 | case HInductionVarAnalysis::kTripCountInLoop: |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 615 | case HInductionVarAnalysis::kTripCountInLoopUnsafe: |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 616 | if (!in_body && !is_min) { // one extra! |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 617 | return GetVal(info->op_a, trip, in_body, is_min); |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 618 | } |
| 619 | FALLTHROUGH_INTENDED; |
| 620 | case HInductionVarAnalysis::kTripCountInBody: |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 621 | case HInductionVarAnalysis::kTripCountInBodyUnsafe: |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 622 | if (is_min) { |
| 623 | return Value(0); |
| 624 | } else if (in_body) { |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 625 | return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1)); |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 626 | } |
| 627 | break; |
| 628 | default: |
| 629 | break; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 630 | } |
| 631 | break; |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 632 | case HInductionVarAnalysis::kLinear: |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 633 | return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 634 | case HInductionVarAnalysis::kWrapAround: |
| 635 | case HInductionVarAnalysis::kPeriodic: |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 636 | return MergeVal(GetVal(info->op_a, trip, in_body, is_min), |
| 637 | GetVal(info->op_b, trip, in_body, is_min), is_min); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 638 | } |
| 639 | } |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 640 | return Value(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 641 | } |
| 642 | |
| 643 | InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1, |
| 644 | HInductionVarAnalysis::InductionInfo* info2, |
| 645 | HInductionVarAnalysis::InductionInfo* trip, |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 646 | bool in_body, |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 647 | bool is_min) const { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 648 | // Constant times range. |
| 649 | int64_t value = 0; |
| 650 | if (IsConstant(info1, kExact, &value)) { |
| 651 | return MulRangeAndConstant(value, info2, trip, in_body, is_min); |
| 652 | } else if (IsConstant(info2, kExact, &value)) { |
| 653 | return MulRangeAndConstant(value, info1, trip, in_body, is_min); |
| 654 | } |
| 655 | // Interval ranges. |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 656 | Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); |
| 657 | Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); |
| 658 | Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); |
| 659 | Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 660 | // Positive range vs. positive or negative range. |
| 661 | if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { |
| 662 | if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { |
| 663 | return is_min ? MulValue(v1_min, v2_min) : MulValue(v1_max, v2_max); |
| 664 | } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { |
| 665 | return is_min ? MulValue(v1_max, v2_min) : MulValue(v1_min, v2_max); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 666 | } |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 667 | } |
| 668 | // Negative range vs. positive or negative range. |
| 669 | if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { |
| 670 | if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { |
| 671 | return is_min ? MulValue(v1_min, v2_max) : MulValue(v1_max, v2_min); |
| 672 | } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { |
| 673 | return is_min ? MulValue(v1_max, v2_max) : MulValue(v1_min, v2_min); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 674 | } |
| 675 | } |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 676 | return Value(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 677 | } |
| 678 | |
| 679 | InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1, |
| 680 | HInductionVarAnalysis::InductionInfo* info2, |
| 681 | HInductionVarAnalysis::InductionInfo* trip, |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 682 | bool in_body, |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 683 | bool is_min) const { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 684 | // Range divided by constant. |
| 685 | int64_t value = 0; |
| 686 | if (IsConstant(info2, kExact, &value)) { |
| 687 | return DivRangeAndConstant(value, info1, trip, in_body, is_min); |
| 688 | } |
| 689 | // Interval ranges. |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 690 | Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); |
| 691 | Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); |
| 692 | Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); |
| 693 | Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 694 | // Positive range vs. positive or negative range. |
| 695 | if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { |
| 696 | if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { |
| 697 | return is_min ? DivValue(v1_min, v2_max) : DivValue(v1_max, v2_min); |
| 698 | } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { |
| 699 | return is_min ? DivValue(v1_max, v2_max) : DivValue(v1_min, v2_min); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 700 | } |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 701 | } |
| 702 | // Negative range vs. positive or negative range. |
| 703 | if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { |
| 704 | if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { |
| 705 | return is_min ? DivValue(v1_min, v2_min) : DivValue(v1_max, v2_max); |
| 706 | } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { |
| 707 | return is_min ? DivValue(v1_max, v2_min) : DivValue(v1_min, v2_max); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 708 | } |
| 709 | } |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 710 | return Value(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 711 | } |
| 712 | |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 713 | InductionVarRange::Value InductionVarRange::GetXor( |
| 714 | HInductionVarAnalysis::InductionInfo* info1, |
| 715 | HInductionVarAnalysis::InductionInfo* info2) const { |
| 716 | int64_t v1 = 0; |
| 717 | int64_t v2 = 0; |
| 718 | // Only accept exact values. |
| 719 | if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2)) { |
| 720 | int64_t value = v1 ^ v2; |
| 721 | if (CanLongValueFitIntoInt(value)) { |
| 722 | return Value(static_cast<int32_t>(value)); |
| 723 | } |
| 724 | } |
| 725 | return Value(); |
| 726 | } |
| 727 | |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 728 | InductionVarRange::Value InductionVarRange::MulRangeAndConstant( |
| 729 | int64_t value, |
| 730 | HInductionVarAnalysis::InductionInfo* info, |
| 731 | HInductionVarAnalysis::InductionInfo* trip, |
| 732 | bool in_body, |
| 733 | bool is_min) const { |
| 734 | if (CanLongValueFitIntoInt(value)) { |
| 735 | Value c(static_cast<int32_t>(value)); |
| 736 | return MulValue(GetVal(info, trip, in_body, is_min == value >= 0), c); |
| 737 | } |
| 738 | return Value(); |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 739 | } |
| 740 | |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 741 | InductionVarRange::Value InductionVarRange::DivRangeAndConstant( |
| 742 | int64_t value, |
| 743 | HInductionVarAnalysis::InductionInfo* info, |
| 744 | HInductionVarAnalysis::InductionInfo* trip, |
| 745 | bool in_body, |
| 746 | bool is_min) const { |
| 747 | if (CanLongValueFitIntoInt(value)) { |
| 748 | Value c(static_cast<int32_t>(value)); |
| 749 | return DivValue(GetVal(info, trip, in_body, is_min == value >= 0), c); |
| 750 | } |
| 751 | return Value(); |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 752 | } |
| 753 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 754 | InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 755 | if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 756 | const int32_t b = v1.b_constant + v2.b_constant; |
| 757 | if (v1.a_constant == 0) { |
| 758 | return Value(v2.instruction, v2.a_constant, b); |
| 759 | } else if (v2.a_constant == 0) { |
| 760 | return Value(v1.instruction, v1.a_constant, b); |
| 761 | } else if (v1.instruction == v2.instruction && IsSafeAdd(v1.a_constant, v2.a_constant)) { |
| 762 | return Value(v1.instruction, v1.a_constant + v2.a_constant, b); |
| 763 | } |
| 764 | } |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 765 | return Value(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 766 | } |
| 767 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 768 | InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) const { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 769 | if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 770 | const int32_t b = v1.b_constant - v2.b_constant; |
| 771 | if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) { |
| 772 | return Value(v2.instruction, -v2.a_constant, b); |
| 773 | } else if (v2.a_constant == 0) { |
| 774 | return Value(v1.instruction, v1.a_constant, b); |
| 775 | } else if (v1.instruction == v2.instruction && IsSafeSub(v1.a_constant, v2.a_constant)) { |
| 776 | return Value(v1.instruction, v1.a_constant - v2.a_constant, b); |
| 777 | } |
| 778 | } |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 779 | return Value(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 780 | } |
| 781 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 782 | InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) const { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 783 | if (v1.is_known && v2.is_known) { |
| 784 | if (v1.a_constant == 0) { |
| 785 | if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { |
| 786 | return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant); |
| 787 | } |
| 788 | } else if (v2.a_constant == 0) { |
| 789 | if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { |
| 790 | return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant); |
| 791 | } |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 792 | } |
| 793 | } |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 794 | return Value(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 795 | } |
| 796 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 797 | InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) const { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 798 | if (v1.is_known && v2.is_known && v1.a_constant == 0 && v2.a_constant == 0) { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 799 | if (IsSafeDiv(v1.b_constant, v2.b_constant)) { |
| 800 | return Value(v1.b_constant / v2.b_constant); |
| 801 | } |
| 802 | } |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 803 | return Value(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 804 | } |
| 805 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 806 | InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) const { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 807 | if (v1.is_known && v2.is_known) { |
| 808 | if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) { |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 809 | return Value(v1.instruction, v1.a_constant, |
| 810 | is_min ? std::min(v1.b_constant, v2.b_constant) |
| 811 | : std::max(v1.b_constant, v2.b_constant)); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 812 | } |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 813 | } |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 814 | return Value(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 815 | } |
| 816 | |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 817 | bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, |
| 818 | HInstruction* instruction, |
| 819 | bool is_last_value, |
| 820 | HGraph* graph, |
| 821 | HBasicBlock* block, |
| 822 | /*out*/HInstruction** lower, |
| 823 | /*out*/HInstruction** upper, |
| 824 | /*out*/HInstruction** taken_test, |
| 825 | /*out*/int64_t* stride_value, |
| 826 | /*out*/bool* needs_finite_test, |
| 827 | /*out*/bool* needs_taken_test) const { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 828 | HLoopInformation* loop = nullptr; |
| 829 | HInductionVarAnalysis::InductionInfo* info = nullptr; |
| 830 | HInductionVarAnalysis::InductionInfo* trip = nullptr; |
| 831 | if (!HasInductionInfo(context, instruction, &loop, &info, &trip) || trip == nullptr) { |
| 832 | return false; // codegen needs all information, including tripcount |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 833 | } |
| 834 | // Determine what tests are needed. A finite test is needed if the evaluation code uses the |
| 835 | // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot" |
| 836 | // the computed range). A taken test is needed for any unknown trip-count, even if evaluation |
| 837 | // code does not use the trip-count explicitly (since there could be an implicit relation |
| 838 | // between e.g. an invariant subscript and a not-taken condition). |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 839 | bool in_body = context->GetBlock() != loop->GetHeader(); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 840 | *stride_value = 0; |
| 841 | *needs_finite_test = NeedsTripCount(info, stride_value) && IsUnsafeTripCount(trip); |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 842 | *needs_taken_test = IsBodyTripCount(trip); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 843 | // Handle last value request. |
| 844 | if (is_last_value) { |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 845 | if (info->induction_class == HInductionVarAnalysis::kLinear) { |
| 846 | if (*stride_value > 0) { |
| 847 | lower = nullptr; |
| 848 | } else { |
| 849 | upper = nullptr; |
| 850 | } |
| 851 | } else if (info->induction_class == HInductionVarAnalysis::kPeriodic) { |
| 852 | DCHECK(!in_body); |
| 853 | return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 854 | } else { |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 855 | return false; |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 856 | } |
| 857 | } |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 858 | // Code generation for taken test: generate the code when requested or otherwise analyze |
| 859 | // if code generation is feasible when taken test is needed. |
| 860 | if (taken_test != nullptr) { |
| 861 | return GenerateCode(trip->op_b, nullptr, graph, block, taken_test, in_body, /* is_min */ false); |
| 862 | } else if (*needs_taken_test) { |
| 863 | if (!GenerateCode( |
| 864 | trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min */ false)) { |
| 865 | return false; |
| 866 | } |
| 867 | } |
| 868 | // Code generation for lower and upper. |
| 869 | return |
| 870 | // Success on lower if invariant (not set), or code can be generated. |
| 871 | ((info->induction_class == HInductionVarAnalysis::kInvariant) || |
| 872 | GenerateCode(info, trip, graph, block, lower, in_body, /* is_min */ true)) && |
| 873 | // And success on upper. |
| 874 | GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 875 | } |
| 876 | |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 877 | bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info, |
| 878 | HInductionVarAnalysis::InductionInfo* trip, |
| 879 | HGraph* graph, |
| 880 | HBasicBlock* block, |
| 881 | /*out*/HInstruction** result, |
| 882 | /*out*/bool* needs_taken_test) const { |
| 883 | DCHECK(info->induction_class == HInductionVarAnalysis::kPeriodic); |
| 884 | // Count period. |
| 885 | int32_t period = 1; |
| 886 | for (HInductionVarAnalysis::InductionInfo* p = info; |
| 887 | p->induction_class == HInductionVarAnalysis::kPeriodic; |
| 888 | p = p->op_b, ++period) {} |
| 889 | // Handle periodic(x, y) case for restricted types. |
| 890 | if (period != 2 || |
| 891 | trip->op_a->type != Primitive::kPrimInt || |
| 892 | (info->type != Primitive::kPrimInt && info->type != Primitive::kPrimBoolean)) { |
| 893 | return false; // TODO: easy to generalize |
| 894 | } |
| 895 | HInstruction* x_instr = nullptr; |
| 896 | HInstruction* y_instr = nullptr; |
| 897 | HInstruction* trip_expr = nullptr; |
| 898 | if (GenerateCode(info->op_a, nullptr, graph, block, graph ? &x_instr : nullptr, false, false) && |
| 899 | GenerateCode(info->op_b, nullptr, graph, block, graph ? &y_instr : nullptr, false, false) && |
| 900 | GenerateCode(trip->op_a, nullptr, graph, block, graph ? &trip_expr : nullptr, false, false)) { |
| 901 | // During actual code generation (graph != nullptr), |
| 902 | // generate is_even ? x : y select instruction. |
| 903 | if (graph != nullptr) { |
| 904 | HInstruction* is_even = Insert(block, new (graph->GetArena()) HEqual( |
| 905 | Insert(block, new (graph->GetArena()) HAnd( |
| 906 | Primitive::kPrimInt, trip_expr, graph->GetIntConstant(1))), |
| 907 | graph->GetIntConstant(0), kNoDexPc)); |
| 908 | *result = Insert(block, new (graph->GetArena()) HSelect(is_even, x_instr, y_instr, kNoDexPc)); |
| 909 | } |
| 910 | // Guard select with taken test if needed. |
| 911 | if (*needs_taken_test) { |
| 912 | HInstruction* taken_test = nullptr; |
| 913 | if (!GenerateCode( |
| 914 | trip->op_b, nullptr, graph, block, graph ? &taken_test : nullptr, false, false)) { |
| 915 | return false; |
| 916 | } else if (graph != nullptr) { |
| 917 | *result = Insert(block, |
| 918 | new (graph->GetArena()) HSelect(taken_test, *result, x_instr, kNoDexPc)); |
| 919 | } |
| 920 | *needs_taken_test = false; // taken care of |
| 921 | } |
| 922 | return true; |
| 923 | } |
| 924 | return false; |
| 925 | } |
| 926 | |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 927 | bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, |
| 928 | HInductionVarAnalysis::InductionInfo* trip, |
| 929 | HGraph* graph, // when set, code is generated |
| 930 | HBasicBlock* block, |
| 931 | /*out*/HInstruction** result, |
| 932 | bool in_body, |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 933 | bool is_min) const { |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 934 | if (info != nullptr) { |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 935 | // If during codegen, the result is not needed (nullptr), simply return success. |
| 936 | if (graph != nullptr && result == nullptr) { |
| 937 | return true; |
| 938 | } |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 939 | // Verify type safety. |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 940 | Primitive::Type type = Primitive::kPrimInt; |
Aart Bik | 639cc8c | 2016-10-18 13:03:31 -0700 | [diff] [blame] | 941 | if (info->type != Primitive::kPrimInt && info->type != Primitive::kPrimBoolean) { |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 942 | return false; |
| 943 | } |
| 944 | // Handle current operation. |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 945 | HInstruction* opa = nullptr; |
| 946 | HInstruction* opb = nullptr; |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 947 | switch (info->induction_class) { |
| 948 | case HInductionVarAnalysis::kInvariant: |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 949 | // Invariants (note that even though is_min does not impact code generation for |
| 950 | // invariants, some effort is made to keep this parameter consistent). |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 951 | switch (info->operation) { |
| 952 | case HInductionVarAnalysis::kAdd: |
Aart Bik | 40fbf74 | 2016-10-31 11:02:50 -0700 | [diff] [blame^] | 953 | case HInductionVarAnalysis::kXor: // no proper is_min for second arg |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 954 | case HInductionVarAnalysis::kLT: |
| 955 | case HInductionVarAnalysis::kLE: |
| 956 | case HInductionVarAnalysis::kGT: |
| 957 | case HInductionVarAnalysis::kGE: |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 958 | if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) && |
| 959 | GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { |
| 960 | if (graph != nullptr) { |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 961 | HInstruction* operation = nullptr; |
| 962 | switch (info->operation) { |
| 963 | case HInductionVarAnalysis::kAdd: |
| 964 | operation = new (graph->GetArena()) HAdd(type, opa, opb); break; |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 965 | case HInductionVarAnalysis::kXor: |
| 966 | operation = new (graph->GetArena()) HXor(type, opa, opb); break; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 967 | case HInductionVarAnalysis::kLT: |
| 968 | operation = new (graph->GetArena()) HLessThan(opa, opb); break; |
| 969 | case HInductionVarAnalysis::kLE: |
| 970 | operation = new (graph->GetArena()) HLessThanOrEqual(opa, opb); break; |
| 971 | case HInductionVarAnalysis::kGT: |
| 972 | operation = new (graph->GetArena()) HGreaterThan(opa, opb); break; |
| 973 | case HInductionVarAnalysis::kGE: |
| 974 | operation = new (graph->GetArena()) HGreaterThanOrEqual(opa, opb); break; |
| 975 | default: |
| 976 | LOG(FATAL) << "unknown operation"; |
| 977 | } |
| 978 | *result = Insert(block, operation); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 979 | } |
| 980 | return true; |
| 981 | } |
| 982 | break; |
| 983 | case HInductionVarAnalysis::kSub: // second reversed! |
| 984 | if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) && |
| 985 | GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) { |
| 986 | if (graph != nullptr) { |
| 987 | *result = Insert(block, new (graph->GetArena()) HSub(type, opa, opb)); |
| 988 | } |
| 989 | return true; |
| 990 | } |
| 991 | break; |
| 992 | case HInductionVarAnalysis::kNeg: // reversed! |
| 993 | if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) { |
| 994 | if (graph != nullptr) { |
| 995 | *result = Insert(block, new (graph->GetArena()) HNeg(type, opb)); |
| 996 | } |
| 997 | return true; |
| 998 | } |
| 999 | break; |
| 1000 | case HInductionVarAnalysis::kFetch: |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 1001 | if (graph != nullptr) { |
| 1002 | *result = info->fetch; // already in HIR |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1003 | } |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 1004 | return true; |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1005 | case HInductionVarAnalysis::kTripCountInLoop: |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 1006 | case HInductionVarAnalysis::kTripCountInLoopUnsafe: |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1007 | if (!in_body && !is_min) { // one extra! |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 1008 | return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1009 | } |
| 1010 | FALLTHROUGH_INTENDED; |
| 1011 | case HInductionVarAnalysis::kTripCountInBody: |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 1012 | case HInductionVarAnalysis::kTripCountInBodyUnsafe: |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1013 | if (is_min) { |
| 1014 | if (graph != nullptr) { |
| 1015 | *result = graph->GetIntConstant(0); |
| 1016 | } |
| 1017 | return true; |
| 1018 | } else if (in_body) { |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 1019 | if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) { |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1020 | if (graph != nullptr) { |
| 1021 | *result = Insert(block, |
| 1022 | new (graph->GetArena()) |
| 1023 | HSub(type, opb, graph->GetIntConstant(1))); |
| 1024 | } |
| 1025 | return true; |
| 1026 | } |
| 1027 | } |
| 1028 | break; |
| 1029 | default: |
| 1030 | break; |
| 1031 | } |
| 1032 | break; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 1033 | case HInductionVarAnalysis::kLinear: { |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 1034 | // Linear induction a * i + b, for normalized 0 <= i < TC. For ranges, this should |
| 1035 | // be restricted to a unit stride to avoid arithmetic wrap-around situations that |
| 1036 | // are harder to guard against. For a last value, requesting min/max based on any |
| 1037 | // stride yields right value. |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 1038 | int64_t stride_value = 0; |
| 1039 | if (IsConstant(info->op_a, kExact, &stride_value)) { |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 1040 | const bool is_min_a = stride_value >= 0 ? is_min : !is_min; |
| 1041 | if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) && |
| 1042 | GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { |
| 1043 | if (graph != nullptr) { |
| 1044 | HInstruction* oper; |
| 1045 | if (stride_value == 1) { |
| 1046 | oper = new (graph->GetArena()) HAdd(type, opa, opb); |
| 1047 | } else if (stride_value == -1) { |
| 1048 | oper = new (graph->GetArena()) HSub(type, opb, opa); |
| 1049 | } else { |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 1050 | HInstruction* mul = new (graph->GetArena()) HMul( |
| 1051 | type, graph->GetIntConstant(stride_value), opa); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 1052 | oper = new (graph->GetArena()) HAdd(type, Insert(block, mul), opb); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1053 | } |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 1054 | *result = Insert(block, oper); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1055 | } |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 1056 | return true; |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1057 | } |
| 1058 | } |
| 1059 | break; |
Aart Bik | 4a34277 | 2015-11-30 10:17:46 -0800 | [diff] [blame] | 1060 | } |
| 1061 | case HInductionVarAnalysis::kWrapAround: |
| 1062 | case HInductionVarAnalysis::kPeriodic: { |
| 1063 | // Wrap-around and periodic inductions are restricted to constants only, so that extreme |
| 1064 | // values are easy to test at runtime without complications of arithmetic wrap-around. |
| 1065 | Value extreme = GetVal(info, trip, in_body, is_min); |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 1066 | if (IsConstantValue(extreme)) { |
Aart Bik | 4a34277 | 2015-11-30 10:17:46 -0800 | [diff] [blame] | 1067 | if (graph != nullptr) { |
| 1068 | *result = graph->GetIntConstant(extreme.b_constant); |
| 1069 | } |
| 1070 | return true; |
| 1071 | } |
| 1072 | break; |
| 1073 | } |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 1074 | default: |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 1075 | break; |
| 1076 | } |
| 1077 | } |
| 1078 | return false; |
| 1079 | } |
| 1080 | |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 1081 | void InductionVarRange::ReplaceInduction(HInductionVarAnalysis::InductionInfo* info, |
| 1082 | HInstruction* fetch, |
| 1083 | HInstruction* replacement) { |
| 1084 | if (info != nullptr) { |
| 1085 | if (info->induction_class == HInductionVarAnalysis::kInvariant && |
| 1086 | info->operation == HInductionVarAnalysis::kFetch && |
| 1087 | info->fetch == fetch) { |
| 1088 | info->fetch = replacement; |
| 1089 | } |
| 1090 | ReplaceInduction(info->op_a, fetch, replacement); |
| 1091 | ReplaceInduction(info->op_b, fetch, replacement); |
| 1092 | } |
| 1093 | } |
| 1094 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1095 | } // namespace art |