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 "base/arena_allocator.h" |
| 18 | #include "builder.h" |
| 19 | #include "gtest/gtest.h" |
| 20 | #include "induction_var_analysis.h" |
| 21 | #include "induction_var_range.h" |
| 22 | #include "nodes.h" |
| 23 | #include "optimizing_unit_test.h" |
| 24 | |
| 25 | namespace art { |
| 26 | |
| 27 | using Value = InductionVarRange::Value; |
| 28 | |
| 29 | /** |
| 30 | * Fixture class for the InductionVarRange tests. |
| 31 | */ |
| 32 | class InductionVarRangeTest : public testing::Test { |
| 33 | public: |
| 34 | InductionVarRangeTest() : pool_(), allocator_(&pool_) { |
| 35 | graph_ = CreateGraph(&allocator_); |
| 36 | iva_ = new (&allocator_) HInductionVarAnalysis(graph_); |
| 37 | BuildGraph(); |
| 38 | } |
| 39 | |
| 40 | ~InductionVarRangeTest() { } |
| 41 | |
| 42 | void ExpectEqual(Value v1, Value v2) { |
| 43 | EXPECT_EQ(v1.instruction, v2.instruction); |
| 44 | EXPECT_EQ(v1.a_constant, v2.a_constant); |
| 45 | EXPECT_EQ(v1.b_constant, v2.b_constant); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 46 | EXPECT_EQ(v1.is_known, v2.is_known); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 47 | } |
| 48 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 49 | // |
| 50 | // Construction methods. |
| 51 | // |
| 52 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 53 | /** Constructs bare minimum graph. */ |
| 54 | void BuildGraph() { |
| 55 | graph_->SetNumberOfVRegs(1); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 56 | entry_block_ = new (&allocator_) HBasicBlock(graph_); |
| 57 | exit_block_ = new (&allocator_) HBasicBlock(graph_); |
| 58 | graph_->AddBlock(entry_block_); |
| 59 | graph_->AddBlock(exit_block_); |
| 60 | graph_->SetEntryBlock(entry_block_); |
| 61 | graph_->SetExitBlock(exit_block_); |
| 62 | } |
| 63 | |
| 64 | /** Constructs loop with given upper bound. */ |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 65 | void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) { |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 66 | // Control flow. |
| 67 | loop_preheader_ = new (&allocator_) HBasicBlock(graph_); |
| 68 | graph_->AddBlock(loop_preheader_); |
| 69 | HBasicBlock* loop_header = new (&allocator_) HBasicBlock(graph_); |
| 70 | graph_->AddBlock(loop_header); |
| 71 | HBasicBlock* loop_body = new (&allocator_) HBasicBlock(graph_); |
| 72 | graph_->AddBlock(loop_body); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 73 | HBasicBlock* return_block = new (&allocator_) HBasicBlock(graph_); |
| 74 | graph_->AddBlock(return_block); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 75 | entry_block_->AddSuccessor(loop_preheader_); |
| 76 | loop_preheader_->AddSuccessor(loop_header); |
| 77 | loop_header->AddSuccessor(loop_body); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 78 | loop_header->AddSuccessor(return_block); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 79 | loop_body->AddSuccessor(loop_header); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 80 | return_block->AddSuccessor(exit_block_); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 81 | // Instructions. |
| 82 | HLocal* induc = new (&allocator_) HLocal(0); |
| 83 | entry_block_->AddInstruction(induc); |
| 84 | loop_preheader_->AddInstruction( |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 85 | new (&allocator_) HStoreLocal(induc, graph_->GetIntConstant(lower))); // i = l |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 86 | loop_preheader_->AddInstruction(new (&allocator_) HGoto()); |
| 87 | HInstruction* load = new (&allocator_) HLoadLocal(induc, Primitive::kPrimInt); |
| 88 | loop_header->AddInstruction(load); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 89 | if (stride > 0) { |
| 90 | condition_ = new (&allocator_) HLessThan(load, upper); // i < u |
| 91 | } else { |
| 92 | condition_ = new (&allocator_) HGreaterThan(load, upper); // i > u |
| 93 | } |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 94 | loop_header->AddInstruction(condition_); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 95 | loop_header->AddInstruction(new (&allocator_) HIf(condition_)); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 96 | load = new (&allocator_) HLoadLocal(induc, Primitive::kPrimInt); |
| 97 | loop_body->AddInstruction(load); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 98 | increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, load, graph_->GetIntConstant(stride)); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 99 | loop_body->AddInstruction(increment_); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 100 | loop_body->AddInstruction(new (&allocator_) HStoreLocal(induc, increment_)); // i += s |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 101 | loop_body->AddInstruction(new (&allocator_) HGoto()); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 102 | return_block->AddInstruction(new (&allocator_) HReturnVoid()); |
| 103 | exit_block_->AddInstruction(new (&allocator_) HExit()); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 104 | } |
| 105 | |
| 106 | /** Performs induction variable analysis. */ |
| 107 | void PerformInductionVarAnalysis() { |
| 108 | ASSERT_TRUE(graph_->TryBuildingSsa()); |
| 109 | iva_->Run(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 110 | } |
| 111 | |
| 112 | /** Constructs an invariant. */ |
| 113 | HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc, |
| 114 | HInductionVarAnalysis::InductionInfo* a, |
| 115 | HInductionVarAnalysis::InductionInfo* b) { |
| 116 | HInductionVarAnalysis::InductionOp op; |
| 117 | switch (opc) { |
| 118 | case '+': op = HInductionVarAnalysis::kAdd; break; |
| 119 | case '-': op = HInductionVarAnalysis::kSub; break; |
| 120 | case 'n': op = HInductionVarAnalysis::kNeg; break; |
| 121 | case '*': op = HInductionVarAnalysis::kMul; break; |
| 122 | case '/': op = HInductionVarAnalysis::kDiv; break; |
| 123 | default: op = HInductionVarAnalysis::kNop; break; |
| 124 | } |
| 125 | return iva_->CreateInvariantOp(op, a, b); |
| 126 | } |
| 127 | |
| 128 | /** Constructs a fetch. */ |
| 129 | HInductionVarAnalysis::InductionInfo* CreateFetch(HInstruction* fetch) { |
| 130 | return iva_->CreateInvariantFetch(fetch); |
| 131 | } |
| 132 | |
| 133 | /** Constructs a constant. */ |
| 134 | HInductionVarAnalysis::InductionInfo* CreateConst(int32_t c) { |
| 135 | return CreateFetch(graph_->GetIntConstant(c)); |
| 136 | } |
| 137 | |
| 138 | /** Constructs a trip-count. */ |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 139 | HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) { |
| 140 | if (in_loop && safe) { |
| 141 | return iva_->CreateTripCount( |
| 142 | HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr); |
| 143 | } else if (in_loop) { |
| 144 | return iva_->CreateTripCount( |
| 145 | HInductionVarAnalysis::kTripCountInLoopUnsafe, CreateConst(tc), nullptr); |
| 146 | } else if (safe) { |
| 147 | return iva_->CreateTripCount( |
| 148 | HInductionVarAnalysis::kTripCountInBody, CreateConst(tc), nullptr); |
| 149 | } else { |
| 150 | return iva_->CreateTripCount( |
| 151 | HInductionVarAnalysis::kTripCountInBodyUnsafe, CreateConst(tc), nullptr); |
| 152 | } |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 153 | } |
| 154 | |
| 155 | /** Constructs a linear a * i + b induction. */ |
| 156 | HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) { |
| 157 | return iva_->CreateInduction(HInductionVarAnalysis::kLinear, CreateConst(a), CreateConst(b)); |
| 158 | } |
| 159 | |
| 160 | /** Constructs a range [lo, hi] using a periodic induction. */ |
| 161 | HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) { |
| 162 | return iva_->CreateInduction( |
| 163 | HInductionVarAnalysis::kPeriodic, CreateConst(lo), CreateConst(hi)); |
| 164 | } |
| 165 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 166 | /** Constructs a wrap-around induction consisting of a constant, followed info */ |
| 167 | HInductionVarAnalysis::InductionInfo* CreateWrapAround( |
| 168 | int32_t initial, |
| 169 | HInductionVarAnalysis::InductionInfo* info) { |
| 170 | return iva_->CreateInduction(HInductionVarAnalysis::kWrapAround, CreateConst(initial), info); |
| 171 | } |
| 172 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 173 | /** Constructs a wrap-around induction consisting of a constant, followed by a range. */ |
| 174 | HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) { |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 175 | return CreateWrapAround(initial, CreateRange(lo, hi)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 176 | } |
| 177 | |
| 178 | // |
| 179 | // Relay methods. |
| 180 | // |
| 181 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 182 | bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) { |
| 183 | return InductionVarRange::NeedsTripCount(info); |
| 184 | } |
| 185 | |
| 186 | bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) { |
| 187 | return InductionVarRange::IsBodyTripCount(trip); |
| 188 | } |
| 189 | |
| 190 | bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) { |
| 191 | return InductionVarRange::IsUnsafeTripCount(trip); |
| 192 | } |
| 193 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 194 | Value GetMin(HInductionVarAnalysis::InductionInfo* info, |
| 195 | HInductionVarAnalysis::InductionInfo* induc) { |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 196 | return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ true); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 197 | } |
| 198 | |
| 199 | Value GetMax(HInductionVarAnalysis::InductionInfo* info, |
| 200 | HInductionVarAnalysis::InductionInfo* induc) { |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 201 | return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ false); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 202 | } |
| 203 | |
| 204 | Value GetMul(HInductionVarAnalysis::InductionInfo* info1, |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 205 | HInductionVarAnalysis::InductionInfo* info2, |
| 206 | bool is_min) { |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 207 | return InductionVarRange::GetMul(info1, info2, nullptr, /* in_body */ true, is_min); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 208 | } |
| 209 | |
| 210 | Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 211 | HInductionVarAnalysis::InductionInfo* info2, |
| 212 | bool is_min) { |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 213 | return InductionVarRange::GetDiv(info1, info2, nullptr, /* in_body */ true, is_min); |
| 214 | } |
| 215 | |
| 216 | bool GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t* value) { |
| 217 | return InductionVarRange::GetConstant(info, value); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 218 | } |
| 219 | |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 220 | Value AddValue(Value v1, Value v2) { return InductionVarRange::AddValue(v1, v2); } |
| 221 | Value SubValue(Value v1, Value v2) { return InductionVarRange::SubValue(v1, v2); } |
| 222 | Value MulValue(Value v1, Value v2) { return InductionVarRange::MulValue(v1, v2); } |
| 223 | Value DivValue(Value v1, Value v2) { return InductionVarRange::DivValue(v1, v2); } |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 224 | Value MinValue(Value v1, Value v2) { return InductionVarRange::MergeVal(v1, v2, true); } |
| 225 | Value MaxValue(Value v1, Value v2) { return InductionVarRange::MergeVal(v1, v2, false); } |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 226 | |
| 227 | // General building fields. |
| 228 | ArenaPool pool_; |
| 229 | ArenaAllocator allocator_; |
| 230 | HGraph* graph_; |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 231 | HBasicBlock* entry_block_; |
| 232 | HBasicBlock* exit_block_; |
| 233 | HBasicBlock* loop_preheader_; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 234 | HInductionVarAnalysis* iva_; |
| 235 | |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 236 | // Instructions. |
| 237 | HInstruction* condition_; |
| 238 | HInstruction* increment_; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 239 | HReturnVoid x_; |
| 240 | HReturnVoid y_; |
| 241 | }; |
| 242 | |
| 243 | // |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 244 | // Tests on static methods. |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 245 | // |
| 246 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 247 | TEST_F(InductionVarRangeTest, TripCountProperties) { |
| 248 | EXPECT_FALSE(NeedsTripCount(nullptr)); |
| 249 | EXPECT_FALSE(NeedsTripCount(CreateConst(1))); |
| 250 | EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1))); |
| 251 | EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3))); |
| 252 | EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1)))); |
| 253 | |
| 254 | EXPECT_FALSE(IsBodyTripCount(nullptr)); |
| 255 | EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true))); |
| 256 | EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false))); |
| 257 | EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true))); |
| 258 | EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false))); |
| 259 | |
| 260 | EXPECT_FALSE(IsUnsafeTripCount(nullptr)); |
| 261 | EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true))); |
| 262 | EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false))); |
| 263 | EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true))); |
| 264 | EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false))); |
| 265 | } |
| 266 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 267 | TEST_F(InductionVarRangeTest, GetMinMaxNull) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 268 | ExpectEqual(Value(), GetMin(nullptr, nullptr)); |
| 269 | ExpectEqual(Value(), GetMax(nullptr, nullptr)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 270 | } |
| 271 | |
| 272 | TEST_F(InductionVarRangeTest, GetMinMaxAdd) { |
| 273 | ExpectEqual(Value(12), |
| 274 | GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 275 | ExpectEqual(Value(22), |
| 276 | GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 277 | ExpectEqual(Value(&x_, 1, -20), |
| 278 | GetMin(CreateInvariant('+', CreateFetch(&x_), CreateRange(-20, -10)), nullptr)); |
| 279 | ExpectEqual(Value(&x_, 1, -10), |
| 280 | GetMax(CreateInvariant('+', CreateFetch(&x_), CreateRange(-20, -10)), nullptr)); |
| 281 | ExpectEqual(Value(&x_, 1, 10), |
| 282 | GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(&x_)), nullptr)); |
| 283 | ExpectEqual(Value(&x_, 1, 20), |
| 284 | GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(&x_)), nullptr)); |
| 285 | ExpectEqual(Value(5), |
| 286 | GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); |
| 287 | ExpectEqual(Value(19), |
| 288 | GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); |
| 289 | } |
| 290 | |
| 291 | TEST_F(InductionVarRangeTest, GetMinMaxSub) { |
| 292 | ExpectEqual(Value(-18), |
| 293 | GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 294 | ExpectEqual(Value(-8), |
| 295 | GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 296 | ExpectEqual(Value(&x_, 1, 10), |
| 297 | GetMin(CreateInvariant('-', CreateFetch(&x_), CreateRange(-20, -10)), nullptr)); |
| 298 | ExpectEqual(Value(&x_, 1, 20), |
| 299 | GetMax(CreateInvariant('-', CreateFetch(&x_), CreateRange(-20, -10)), nullptr)); |
| 300 | ExpectEqual(Value(&x_, -1, 10), |
| 301 | GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(&x_)), nullptr)); |
| 302 | ExpectEqual(Value(&x_, -1, 20), |
| 303 | GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(&x_)), nullptr)); |
| 304 | ExpectEqual(Value(-25), |
| 305 | GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); |
| 306 | ExpectEqual(Value(-11), |
| 307 | GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); |
| 308 | } |
| 309 | |
| 310 | TEST_F(InductionVarRangeTest, GetMinMaxNeg) { |
| 311 | ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); |
| 312 | ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); |
| 313 | ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); |
| 314 | ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); |
| 315 | ExpectEqual(Value(&x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(&x_)), nullptr)); |
| 316 | ExpectEqual(Value(&x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(&x_)), nullptr)); |
| 317 | } |
| 318 | |
| 319 | TEST_F(InductionVarRangeTest, GetMinMaxMul) { |
| 320 | ExpectEqual(Value(20), |
| 321 | GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 322 | ExpectEqual(Value(40), |
| 323 | GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 324 | } |
| 325 | |
| 326 | TEST_F(InductionVarRangeTest, GetMinMaxDiv) { |
| 327 | ExpectEqual(Value(3), |
| 328 | GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); |
| 329 | ExpectEqual(Value(5), |
| 330 | GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); |
| 331 | } |
| 332 | |
| 333 | TEST_F(InductionVarRangeTest, GetMinMaxConstant) { |
| 334 | ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr)); |
| 335 | ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr)); |
| 336 | } |
| 337 | |
| 338 | TEST_F(InductionVarRangeTest, GetMinMaxFetch) { |
| 339 | ExpectEqual(Value(&x_, 1, 0), GetMin(CreateFetch(&x_), nullptr)); |
| 340 | ExpectEqual(Value(&x_, 1, 0), GetMax(CreateFetch(&x_), nullptr)); |
| 341 | } |
| 342 | |
| 343 | TEST_F(InductionVarRangeTest, GetMinMaxLinear) { |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 344 | ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100, true, true))); |
| 345 | ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100, true, true))); |
| 346 | ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100, true, true))); |
| 347 | ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100, true, true))); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 348 | } |
| 349 | |
| 350 | TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) { |
| 351 | ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr)); |
| 352 | ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr)); |
| 353 | ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr)); |
| 354 | ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr)); |
| 355 | ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr)); |
| 356 | ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr)); |
| 357 | } |
| 358 | |
| 359 | TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) { |
| 360 | ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr)); |
| 361 | ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr)); |
| 362 | } |
| 363 | |
| 364 | TEST_F(InductionVarRangeTest, GetMulMin) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 365 | ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true)); |
| 366 | ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true)); |
| 367 | ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true)); |
| 368 | ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 369 | } |
| 370 | |
| 371 | TEST_F(InductionVarRangeTest, GetMulMax) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 372 | ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false)); |
| 373 | ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false)); |
| 374 | ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false)); |
| 375 | ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 376 | } |
| 377 | |
| 378 | TEST_F(InductionVarRangeTest, GetDivMin) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 379 | ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true)); |
| 380 | ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true)); |
| 381 | ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true)); |
| 382 | ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 383 | } |
| 384 | |
| 385 | TEST_F(InductionVarRangeTest, GetDivMax) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 386 | ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false)); |
| 387 | ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false)); |
| 388 | ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false)); |
| 389 | ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 390 | } |
| 391 | |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 392 | TEST_F(InductionVarRangeTest, GetConstant) { |
| 393 | int32_t value; |
| 394 | ASSERT_TRUE(GetConstant(CreateConst(12345), &value)); |
| 395 | EXPECT_EQ(12345, value); |
| 396 | EXPECT_FALSE(GetConstant(CreateRange(1, 2), &value)); |
| 397 | } |
| 398 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 399 | TEST_F(InductionVarRangeTest, AddValue) { |
| 400 | ExpectEqual(Value(110), AddValue(Value(10), Value(100))); |
| 401 | ExpectEqual(Value(-5), AddValue(Value(&x_, 1, -4), Value(&x_, -1, -1))); |
| 402 | ExpectEqual(Value(&x_, 3, -5), AddValue(Value(&x_, 2, -4), Value(&x_, 1, -1))); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 403 | ExpectEqual(Value(), AddValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 404 | ExpectEqual(Value(&x_, 1, 23), AddValue(Value(&x_, 1, 20), Value(3))); |
| 405 | ExpectEqual(Value(&y_, 1, 5), AddValue(Value(55), Value(&y_, 1, -50))); |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 406 | const int32_t max_value = std::numeric_limits<int32_t>::max(); |
| 407 | ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5))); |
| 408 | ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 409 | } |
| 410 | |
| 411 | TEST_F(InductionVarRangeTest, SubValue) { |
| 412 | ExpectEqual(Value(-90), SubValue(Value(10), Value(100))); |
| 413 | ExpectEqual(Value(-3), SubValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); |
| 414 | ExpectEqual(Value(&x_, 2, -3), SubValue(Value(&x_, 3, -4), Value(&x_, 1, -1))); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 415 | ExpectEqual(Value(), SubValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 416 | ExpectEqual(Value(&x_, 1, 17), SubValue(Value(&x_, 1, 20), Value(3))); |
| 417 | ExpectEqual(Value(&y_, -4, 105), SubValue(Value(55), Value(&y_, 4, -50))); |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 418 | const int32_t min_value = std::numeric_limits<int32_t>::min(); |
| 419 | ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5))); |
| 420 | ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 421 | } |
| 422 | |
| 423 | TEST_F(InductionVarRangeTest, MulValue) { |
| 424 | ExpectEqual(Value(1000), MulValue(Value(10), Value(100))); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 425 | ExpectEqual(Value(), MulValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); |
| 426 | ExpectEqual(Value(), MulValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 427 | ExpectEqual(Value(&x_, 9, 60), MulValue(Value(&x_, 3, 20), Value(3))); |
| 428 | ExpectEqual(Value(&y_, 55, -110), MulValue(Value(55), Value(&y_, 1, -2))); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 429 | ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 430 | } |
| 431 | |
| 432 | TEST_F(InductionVarRangeTest, DivValue) { |
| 433 | ExpectEqual(Value(25), DivValue(Value(100), Value(4))); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 434 | ExpectEqual(Value(), DivValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); |
| 435 | ExpectEqual(Value(), DivValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); |
| 436 | ExpectEqual(Value(), DivValue(Value(&x_, 12, 24), Value(3))); |
| 437 | ExpectEqual(Value(), DivValue(Value(55), Value(&y_, 1, -50))); |
| 438 | ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 439 | } |
| 440 | |
| 441 | TEST_F(InductionVarRangeTest, MinValue) { |
| 442 | ExpectEqual(Value(10), MinValue(Value(10), Value(100))); |
| 443 | ExpectEqual(Value(&x_, 1, -4), MinValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); |
| 444 | ExpectEqual(Value(&x_, 4, -4), MinValue(Value(&x_, 4, -4), Value(&x_, 4, -1))); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 445 | ExpectEqual(Value(), MinValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); |
| 446 | ExpectEqual(Value(), MinValue(Value(&x_, 1, 20), Value(3))); |
| 447 | ExpectEqual(Value(), MinValue(Value(55), Value(&y_, 1, -50))); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 448 | } |
| 449 | |
| 450 | TEST_F(InductionVarRangeTest, MaxValue) { |
| 451 | ExpectEqual(Value(100), MaxValue(Value(10), Value(100))); |
| 452 | ExpectEqual(Value(&x_, 1, -1), MaxValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); |
| 453 | ExpectEqual(Value(&x_, 4, -1), MaxValue(Value(&x_, 4, -4), Value(&x_, 4, -1))); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 454 | ExpectEqual(Value(), MaxValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); |
| 455 | ExpectEqual(Value(), MaxValue(Value(&x_, 1, 20), Value(3))); |
| 456 | ExpectEqual(Value(), MaxValue(Value(55), Value(&y_, 1, -50))); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 457 | } |
| 458 | |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 459 | // |
| 460 | // Tests on instance methods. |
| 461 | // |
| 462 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 463 | TEST_F(InductionVarRangeTest, ConstantTripCountUp) { |
| 464 | BuildLoop(0, graph_->GetIntConstant(1000), 1); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 465 | PerformInductionVarAnalysis(); |
| 466 | InductionVarRange range(iva_); |
| 467 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 468 | Value v1, v2; |
| 469 | bool needs_finite_test = true; |
| 470 | |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 471 | // In context of header: known. |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 472 | range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); |
| 473 | EXPECT_FALSE(needs_finite_test); |
| 474 | ExpectEqual(Value(0), v1); |
| 475 | ExpectEqual(Value(1000), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 476 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 477 | |
| 478 | // In context of loop-body: known. |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 479 | range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); |
| 480 | EXPECT_FALSE(needs_finite_test); |
| 481 | ExpectEqual(Value(0), v1); |
| 482 | ExpectEqual(Value(999), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 483 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 484 | range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); |
| 485 | EXPECT_FALSE(needs_finite_test); |
| 486 | ExpectEqual(Value(1), v1); |
| 487 | ExpectEqual(Value(1000), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 488 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 489 | } |
| 490 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 491 | TEST_F(InductionVarRangeTest, ConstantTripCountDown) { |
| 492 | BuildLoop(1000, graph_->GetIntConstant(0), -1); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 493 | PerformInductionVarAnalysis(); |
| 494 | InductionVarRange range(iva_); |
| 495 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 496 | Value v1, v2; |
| 497 | bool needs_finite_test = true; |
| 498 | |
| 499 | // In context of header: known. |
| 500 | range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); |
| 501 | EXPECT_FALSE(needs_finite_test); |
| 502 | ExpectEqual(Value(0), v1); |
| 503 | ExpectEqual(Value(1000), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 504 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 505 | |
| 506 | // In context of loop-body: known. |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 507 | range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); |
| 508 | EXPECT_FALSE(needs_finite_test); |
| 509 | ExpectEqual(Value(1), v1); |
| 510 | ExpectEqual(Value(1000), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 511 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 512 | range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); |
| 513 | EXPECT_FALSE(needs_finite_test); |
| 514 | ExpectEqual(Value(0), v1); |
| 515 | ExpectEqual(Value(999), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 516 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 517 | } |
| 518 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 519 | TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { |
Calin Juravle | 27cfad0 | 2015-10-20 11:29:36 +0100 | [diff] [blame] | 520 | HInstruction* parameter = new (&allocator_) HParameterValue( |
| 521 | graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 522 | entry_block_->AddInstruction(parameter); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 523 | BuildLoop(0, parameter, 1); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 524 | PerformInductionVarAnalysis(); |
| 525 | InductionVarRange range(iva_); |
| 526 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 527 | Value v1, v2; |
| 528 | bool needs_finite_test = true; |
| 529 | bool needs_taken_test = true; |
| 530 | |
| 531 | // In context of header: upper unknown. |
| 532 | range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); |
| 533 | EXPECT_FALSE(needs_finite_test); |
| 534 | ExpectEqual(Value(0), v1); |
| 535 | ExpectEqual(Value(), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 536 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 537 | |
| 538 | // In context of loop-body: known. |
| 539 | range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); |
| 540 | EXPECT_FALSE(needs_finite_test); |
| 541 | ExpectEqual(Value(0), v1); |
| 542 | ExpectEqual(Value(parameter, 1, -1), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 543 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 544 | range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); |
| 545 | EXPECT_FALSE(needs_finite_test); |
| 546 | ExpectEqual(Value(1), v1); |
| 547 | ExpectEqual(Value(parameter, 1, 0), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 548 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 549 | |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 550 | HInstruction* lower = nullptr; |
| 551 | HInstruction* upper = nullptr; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 552 | HInstruction* taken = nullptr; |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 553 | |
| 554 | // Can generate code in context of loop-body only. |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 555 | EXPECT_FALSE(range.CanGenerateCode( |
| 556 | condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); |
| 557 | ASSERT_TRUE(range.CanGenerateCode( |
| 558 | increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); |
| 559 | EXPECT_FALSE(needs_finite_test); |
| 560 | EXPECT_TRUE(needs_taken_test); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 561 | |
| 562 | // Generates code. |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 563 | range.GenerateRangeCode(increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 564 | |
| 565 | // Verify lower is 0+0. |
| 566 | ASSERT_TRUE(lower != nullptr); |
| 567 | ASSERT_TRUE(lower->IsAdd()); |
| 568 | ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); |
| 569 | EXPECT_EQ(0, lower->InputAt(0)->AsIntConstant()->GetValue()); |
| 570 | ASSERT_TRUE(lower->InputAt(1)->IsIntConstant()); |
| 571 | EXPECT_EQ(0, lower->InputAt(1)->AsIntConstant()->GetValue()); |
| 572 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 573 | // Verify upper is (V-1)+0. |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 574 | ASSERT_TRUE(upper != nullptr); |
| 575 | ASSERT_TRUE(upper->IsAdd()); |
| 576 | ASSERT_TRUE(upper->InputAt(0)->IsSub()); |
| 577 | EXPECT_TRUE(upper->InputAt(0)->InputAt(0)->IsParameterValue()); |
| 578 | ASSERT_TRUE(upper->InputAt(0)->InputAt(1)->IsIntConstant()); |
| 579 | EXPECT_EQ(1, upper->InputAt(0)->InputAt(1)->AsIntConstant()->GetValue()); |
| 580 | ASSERT_TRUE(upper->InputAt(1)->IsIntConstant()); |
| 581 | EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue()); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 582 | |
| 583 | // Verify taken-test is 0<V. |
| 584 | range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken); |
| 585 | ASSERT_TRUE(taken != nullptr); |
| 586 | ASSERT_TRUE(taken->IsLessThan()); |
| 587 | ASSERT_TRUE(taken->InputAt(0)->IsIntConstant()); |
| 588 | EXPECT_EQ(0, taken->InputAt(0)->AsIntConstant()->GetValue()); |
| 589 | EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); |
| 590 | } |
| 591 | |
| 592 | TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { |
| 593 | HInstruction* parameter = new (&allocator_) HParameterValue( |
| 594 | graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); |
| 595 | entry_block_->AddInstruction(parameter); |
| 596 | BuildLoop(1000, parameter, -1); |
| 597 | PerformInductionVarAnalysis(); |
| 598 | InductionVarRange range(iva_); |
| 599 | |
| 600 | Value v1, v2; |
| 601 | bool needs_finite_test = true; |
| 602 | bool needs_taken_test = true; |
| 603 | |
| 604 | // In context of header: lower unknown. |
| 605 | range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); |
| 606 | EXPECT_FALSE(needs_finite_test); |
| 607 | ExpectEqual(Value(), v1); |
| 608 | ExpectEqual(Value(1000), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 609 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 610 | |
| 611 | // In context of loop-body: known. |
| 612 | range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); |
| 613 | EXPECT_FALSE(needs_finite_test); |
| 614 | ExpectEqual(Value(parameter, 1, 1), v1); |
| 615 | ExpectEqual(Value(1000), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 616 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 617 | range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); |
| 618 | EXPECT_FALSE(needs_finite_test); |
| 619 | ExpectEqual(Value(parameter, 1, 0), v1); |
| 620 | ExpectEqual(Value(999), v2); |
Aart Bik | b738d4f | 2015-12-03 11:23:35 -0800 | [diff] [blame] | 621 | EXPECT_FALSE(range.RefineOuter(&v1, &v2)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 622 | |
| 623 | HInstruction* lower = nullptr; |
| 624 | HInstruction* upper = nullptr; |
| 625 | HInstruction* taken = nullptr; |
| 626 | |
| 627 | // Can generate code in context of loop-body only. |
| 628 | EXPECT_FALSE(range.CanGenerateCode( |
| 629 | condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); |
| 630 | ASSERT_TRUE(range.CanGenerateCode( |
| 631 | increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); |
| 632 | EXPECT_FALSE(needs_finite_test); |
| 633 | EXPECT_TRUE(needs_taken_test); |
| 634 | |
| 635 | // Generates code. |
| 636 | range.GenerateRangeCode(increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper); |
| 637 | |
| 638 | // Verify lower is 1000-(-(V-1000)-1). |
| 639 | ASSERT_TRUE(lower != nullptr); |
| 640 | ASSERT_TRUE(lower->IsSub()); |
| 641 | ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); |
| 642 | EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue()); |
| 643 | lower = lower->InputAt(1); |
| 644 | ASSERT_TRUE(lower->IsSub()); |
| 645 | ASSERT_TRUE(lower->InputAt(1)->IsIntConstant()); |
| 646 | EXPECT_EQ(1, lower->InputAt(1)->AsIntConstant()->GetValue()); |
| 647 | lower = lower->InputAt(0); |
| 648 | ASSERT_TRUE(lower->IsNeg()); |
| 649 | lower = lower->InputAt(0); |
| 650 | ASSERT_TRUE(lower->IsSub()); |
| 651 | EXPECT_TRUE(lower->InputAt(0)->IsParameterValue()); |
| 652 | ASSERT_TRUE(lower->InputAt(1)->IsIntConstant()); |
| 653 | EXPECT_EQ(1000, lower->InputAt(1)->AsIntConstant()->GetValue()); |
| 654 | |
| 655 | // Verify upper is 1000-0. |
| 656 | ASSERT_TRUE(upper != nullptr); |
| 657 | ASSERT_TRUE(upper->IsSub()); |
| 658 | ASSERT_TRUE(upper->InputAt(0)->IsIntConstant()); |
| 659 | EXPECT_EQ(1000, upper->InputAt(0)->AsIntConstant()->GetValue()); |
| 660 | ASSERT_TRUE(upper->InputAt(1)->IsIntConstant()); |
| 661 | EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue()); |
| 662 | |
| 663 | // Verify taken-test is 1000>V. |
| 664 | range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken); |
| 665 | ASSERT_TRUE(taken != nullptr); |
| 666 | ASSERT_TRUE(taken->IsGreaterThan()); |
| 667 | ASSERT_TRUE(taken->InputAt(0)->IsIntConstant()); |
| 668 | EXPECT_EQ(1000, taken->InputAt(0)->AsIntConstant()->GetValue()); |
| 669 | EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 670 | } |
| 671 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 672 | } // namespace art |