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" |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 19 | #include "induction_var_analysis.h" |
| 20 | #include "induction_var_range.h" |
| 21 | #include "nodes.h" |
| 22 | #include "optimizing_unit_test.h" |
| 23 | |
| 24 | namespace art { |
| 25 | |
| 26 | using Value = InductionVarRange::Value; |
| 27 | |
| 28 | /** |
| 29 | * Fixture class for the InductionVarRange tests. |
| 30 | */ |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 31 | class InductionVarRangeTest : public CommonCompilerTest { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 32 | public: |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 33 | InductionVarRangeTest() |
| 34 | : pool_(), |
| 35 | allocator_(&pool_), |
| 36 | graph_(CreateGraph(&allocator_)), |
| 37 | iva_(new (&allocator_) HInductionVarAnalysis(graph_)), |
| 38 | range_(iva_) { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 39 | BuildGraph(); |
| 40 | } |
| 41 | |
| 42 | ~InductionVarRangeTest() { } |
| 43 | |
| 44 | void ExpectEqual(Value v1, Value v2) { |
| 45 | EXPECT_EQ(v1.instruction, v2.instruction); |
| 46 | EXPECT_EQ(v1.a_constant, v2.a_constant); |
| 47 | EXPECT_EQ(v1.b_constant, v2.b_constant); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 48 | EXPECT_EQ(v1.is_known, v2.is_known); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 49 | } |
| 50 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 51 | // |
| 52 | // Construction methods. |
| 53 | // |
| 54 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 55 | /** Constructs bare minimum graph. */ |
| 56 | void BuildGraph() { |
| 57 | graph_->SetNumberOfVRegs(1); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 58 | entry_block_ = new (&allocator_) HBasicBlock(graph_); |
| 59 | exit_block_ = new (&allocator_) HBasicBlock(graph_); |
| 60 | graph_->AddBlock(entry_block_); |
| 61 | graph_->AddBlock(exit_block_); |
| 62 | graph_->SetEntryBlock(entry_block_); |
| 63 | graph_->SetExitBlock(exit_block_); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 64 | // Two parameters. |
Andreas Gampe | a5b09a6 | 2016-11-17 15:21:22 -0800 | [diff] [blame] | 65 | x_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), |
| 66 | dex::TypeIndex(0), |
| 67 | 0, |
| 68 | Primitive::kPrimInt); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 69 | entry_block_->AddInstruction(x_); |
Andreas Gampe | a5b09a6 | 2016-11-17 15:21:22 -0800 | [diff] [blame] | 70 | y_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), |
| 71 | dex::TypeIndex(0), |
| 72 | 0, |
| 73 | Primitive::kPrimInt); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 74 | entry_block_->AddInstruction(y_); |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 75 | // Set arbitrary range analysis hint while testing private methods. |
| 76 | SetHint(x_); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 77 | } |
| 78 | |
| 79 | /** Constructs loop with given upper bound. */ |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 80 | void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) { |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 81 | // Control flow. |
| 82 | loop_preheader_ = new (&allocator_) HBasicBlock(graph_); |
| 83 | graph_->AddBlock(loop_preheader_); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 84 | loop_header_ = new (&allocator_) HBasicBlock(graph_); |
| 85 | graph_->AddBlock(loop_header_); |
| 86 | loop_body_ = new (&allocator_) HBasicBlock(graph_); |
| 87 | graph_->AddBlock(loop_body_); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 88 | HBasicBlock* return_block = new (&allocator_) HBasicBlock(graph_); |
| 89 | graph_->AddBlock(return_block); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 90 | entry_block_->AddSuccessor(loop_preheader_); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 91 | loop_preheader_->AddSuccessor(loop_header_); |
| 92 | loop_header_->AddSuccessor(loop_body_); |
| 93 | loop_header_->AddSuccessor(return_block); |
| 94 | loop_body_->AddSuccessor(loop_header_); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 95 | return_block->AddSuccessor(exit_block_); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 96 | // Instructions. |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 97 | loop_preheader_->AddInstruction(new (&allocator_) HGoto()); |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 98 | HPhi* phi = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 99 | loop_header_->AddPhi(phi); |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 100 | phi->AddInput(graph_->GetIntConstant(lower)); // i = l |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 101 | if (stride > 0) { |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 102 | condition_ = new (&allocator_) HLessThan(phi, upper); // i < u |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 103 | } else { |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 104 | condition_ = new (&allocator_) HGreaterThan(phi, upper); // i > u |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 105 | } |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 106 | loop_header_->AddInstruction(condition_); |
| 107 | loop_header_->AddInstruction(new (&allocator_) HIf(condition_)); |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 108 | increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, phi, graph_->GetIntConstant(stride)); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 109 | loop_body_->AddInstruction(increment_); // i += s |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 110 | phi->AddInput(increment_); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 111 | loop_body_->AddInstruction(new (&allocator_) HGoto()); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 112 | return_block->AddInstruction(new (&allocator_) HReturnVoid()); |
| 113 | exit_block_->AddInstruction(new (&allocator_) HExit()); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 114 | } |
| 115 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 116 | /** Constructs SSA and performs induction variable analysis. */ |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 117 | void PerformInductionVarAnalysis() { |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 118 | graph_->BuildDominatorTree(); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 119 | iva_->Run(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 120 | } |
| 121 | |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 122 | /** Sets hint. */ |
| 123 | void SetHint(HInstruction* hint) { |
| 124 | range_.chase_hint_ = hint; |
| 125 | } |
| 126 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 127 | /** Constructs an invariant. */ |
| 128 | HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc, |
| 129 | HInductionVarAnalysis::InductionInfo* a, |
| 130 | HInductionVarAnalysis::InductionInfo* b) { |
| 131 | HInductionVarAnalysis::InductionOp op; |
| 132 | switch (opc) { |
| 133 | case '+': op = HInductionVarAnalysis::kAdd; break; |
| 134 | case '-': op = HInductionVarAnalysis::kSub; break; |
| 135 | case 'n': op = HInductionVarAnalysis::kNeg; break; |
| 136 | case '*': op = HInductionVarAnalysis::kMul; break; |
| 137 | case '/': op = HInductionVarAnalysis::kDiv; break; |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 138 | case '%': op = HInductionVarAnalysis::kRem; break; |
| 139 | case '^': op = HInductionVarAnalysis::kXor; break; |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 140 | case '<': op = HInductionVarAnalysis::kLT; break; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 141 | default: op = HInductionVarAnalysis::kNop; break; |
| 142 | } |
| 143 | return iva_->CreateInvariantOp(op, a, b); |
| 144 | } |
| 145 | |
| 146 | /** Constructs a fetch. */ |
| 147 | HInductionVarAnalysis::InductionInfo* CreateFetch(HInstruction* fetch) { |
| 148 | return iva_->CreateInvariantFetch(fetch); |
| 149 | } |
| 150 | |
| 151 | /** Constructs a constant. */ |
| 152 | HInductionVarAnalysis::InductionInfo* CreateConst(int32_t c) { |
| 153 | return CreateFetch(graph_->GetIntConstant(c)); |
| 154 | } |
| 155 | |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 156 | /** Constructs a constant trip-count. */ |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 157 | HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 158 | HInductionVarAnalysis::InductionOp op = HInductionVarAnalysis::kTripCountInBodyUnsafe; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 159 | if (in_loop && safe) { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 160 | op = HInductionVarAnalysis::kTripCountInLoop; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 161 | } else if (in_loop) { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 162 | op = HInductionVarAnalysis::kTripCountInLoopUnsafe; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 163 | } else if (safe) { |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 164 | op = HInductionVarAnalysis::kTripCountInBody; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 165 | } |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 166 | // Return TC with taken-test 0 < TC. |
| 167 | return iva_->CreateTripCount(op, |
| 168 | CreateConst(tc), |
| 169 | CreateInvariant('<', CreateConst(0), CreateConst(tc)), |
| 170 | Primitive::kPrimInt); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 171 | } |
| 172 | |
| 173 | /** Constructs a linear a * i + b induction. */ |
| 174 | HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 175 | return iva_->CreateInduction(HInductionVarAnalysis::kLinear, |
| 176 | HInductionVarAnalysis::kNop, |
| 177 | CreateConst(a), |
| 178 | CreateConst(b), |
| 179 | nullptr, |
| 180 | Primitive::kPrimInt); |
| 181 | } |
| 182 | |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 183 | /** Constructs a polynomial sum(a * i + b) + c induction. */ |
| 184 | HInductionVarAnalysis::InductionInfo* CreatePolynomial(int32_t a, int32_t b, int32_t c) { |
| 185 | return iva_->CreateInduction(HInductionVarAnalysis::kPolynomial, |
| 186 | HInductionVarAnalysis::kNop, |
| 187 | CreateLinear(a, b), |
| 188 | CreateConst(c), |
| 189 | nullptr, |
| 190 | Primitive::kPrimInt); |
| 191 | } |
| 192 | |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 193 | /** Constructs a geometric a * f^i + b induction. */ |
| 194 | HInductionVarAnalysis::InductionInfo* CreateGeometric(int32_t a, int32_t b, int32_t f, char op) { |
| 195 | return iva_->CreateInduction(HInductionVarAnalysis::kGeometric, |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 196 | op == '*' ? HInductionVarAnalysis::kMul |
| 197 | : HInductionVarAnalysis::kDiv, |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 198 | CreateConst(a), |
| 199 | CreateConst(b), |
| 200 | graph_->GetIntConstant(f), |
| 201 | Primitive::kPrimInt); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 202 | } |
| 203 | |
| 204 | /** Constructs a range [lo, hi] using a periodic induction. */ |
| 205 | HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 206 | return iva_->CreateInduction(HInductionVarAnalysis::kPeriodic, |
| 207 | HInductionVarAnalysis::kNop, |
| 208 | CreateConst(lo), |
| 209 | CreateConst(hi), |
| 210 | nullptr, |
| 211 | Primitive::kPrimInt); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 212 | } |
| 213 | |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 214 | /** Constructs a wrap-around induction consisting of a constant, followed by info. */ |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 215 | HInductionVarAnalysis::InductionInfo* CreateWrapAround( |
| 216 | int32_t initial, |
| 217 | HInductionVarAnalysis::InductionInfo* info) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 218 | return iva_->CreateInduction(HInductionVarAnalysis::kWrapAround, |
| 219 | HInductionVarAnalysis::kNop, |
| 220 | CreateConst(initial), |
| 221 | info, |
| 222 | nullptr, |
| 223 | Primitive::kPrimInt); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 224 | } |
| 225 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 226 | /** Constructs a wrap-around induction consisting of a constant, followed by a range. */ |
| 227 | HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) { |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 228 | return CreateWrapAround(initial, CreateRange(lo, hi)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 229 | } |
| 230 | |
| 231 | // |
| 232 | // Relay methods. |
| 233 | // |
| 234 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 235 | bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) { |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 236 | int64_t s = 0; |
| 237 | return range_.NeedsTripCount(info, &s); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 238 | } |
| 239 | |
| 240 | bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 241 | return range_.IsBodyTripCount(trip); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 242 | } |
| 243 | |
| 244 | bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 245 | return range_.IsUnsafeTripCount(trip); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 246 | } |
| 247 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 248 | Value GetMin(HInductionVarAnalysis::InductionInfo* info, |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 249 | HInductionVarAnalysis::InductionInfo* trip) { |
| 250 | return range_.GetVal(info, trip, /* in_body */ true, /* is_min */ true); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 251 | } |
| 252 | |
| 253 | Value GetMax(HInductionVarAnalysis::InductionInfo* info, |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 254 | HInductionVarAnalysis::InductionInfo* trip) { |
| 255 | return range_.GetVal(info, trip, /* in_body */ true, /* is_min */ false); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 256 | } |
| 257 | |
| 258 | Value GetMul(HInductionVarAnalysis::InductionInfo* info1, |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 259 | HInductionVarAnalysis::InductionInfo* info2, |
| 260 | bool is_min) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 261 | return range_.GetMul(info1, info2, nullptr, /* in_body */ true, is_min); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 262 | } |
| 263 | |
| 264 | Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 265 | HInductionVarAnalysis::InductionInfo* info2, |
| 266 | bool is_min) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 267 | return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min); |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 268 | } |
| 269 | |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 270 | Value GetRem(HInductionVarAnalysis::InductionInfo* info1, |
| 271 | HInductionVarAnalysis::InductionInfo* info2) { |
| 272 | return range_.GetRem(info1, info2); |
| 273 | } |
| 274 | |
| 275 | Value GetXor(HInductionVarAnalysis::InductionInfo* info1, |
| 276 | HInductionVarAnalysis::InductionInfo* info2) { |
| 277 | return range_.GetXor(info1, info2); |
| 278 | } |
| 279 | |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 280 | bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { |
| 281 | return range_.IsConstant(info, InductionVarRange::kExact, value); |
| 282 | } |
| 283 | |
| 284 | bool IsAtMost(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { |
| 285 | return range_.IsConstant(info, InductionVarRange::kAtMost, value); |
| 286 | } |
| 287 | |
| 288 | bool IsAtLeast(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { |
| 289 | return range_.IsConstant(info, InductionVarRange::kAtLeast, value); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 290 | } |
| 291 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 292 | Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); } |
| 293 | Value SubValue(Value v1, Value v2) { return range_.SubValue(v1, v2); } |
| 294 | Value MulValue(Value v1, Value v2) { return range_.MulValue(v1, v2); } |
| 295 | Value DivValue(Value v1, Value v2) { return range_.DivValue(v1, v2); } |
| 296 | Value MinValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, true); } |
| 297 | Value MaxValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, false); } |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 298 | |
| 299 | // General building fields. |
| 300 | ArenaPool pool_; |
| 301 | ArenaAllocator allocator_; |
| 302 | HGraph* graph_; |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 303 | HBasicBlock* entry_block_; |
| 304 | HBasicBlock* exit_block_; |
| 305 | HBasicBlock* loop_preheader_; |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 306 | HBasicBlock* loop_header_; |
| 307 | HBasicBlock* loop_body_; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 308 | HInductionVarAnalysis* iva_; |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 309 | InductionVarRange range_; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 310 | |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 311 | // Instructions. |
| 312 | HInstruction* condition_; |
| 313 | HInstruction* increment_; |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 314 | HInstruction* x_; |
| 315 | HInstruction* y_; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 316 | }; |
| 317 | |
| 318 | // |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 319 | // Tests on private methods. |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 320 | // |
| 321 | |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 322 | TEST_F(InductionVarRangeTest, IsConstant) { |
| 323 | int64_t value; |
| 324 | // Constant. |
| 325 | EXPECT_TRUE(IsExact(CreateConst(12345), &value)); |
| 326 | EXPECT_EQ(12345, value); |
| 327 | EXPECT_TRUE(IsAtMost(CreateConst(12345), &value)); |
| 328 | EXPECT_EQ(12345, value); |
| 329 | EXPECT_TRUE(IsAtLeast(CreateConst(12345), &value)); |
| 330 | EXPECT_EQ(12345, value); |
| 331 | // Constant trivial range. |
| 332 | EXPECT_TRUE(IsExact(CreateRange(111, 111), &value)); |
| 333 | EXPECT_EQ(111, value); |
| 334 | EXPECT_TRUE(IsAtMost(CreateRange(111, 111), &value)); |
| 335 | EXPECT_EQ(111, value); |
| 336 | EXPECT_TRUE(IsAtLeast(CreateRange(111, 111), &value)); |
| 337 | EXPECT_EQ(111, value); |
| 338 | // Constant non-trivial range. |
| 339 | EXPECT_FALSE(IsExact(CreateRange(11, 22), &value)); |
| 340 | EXPECT_TRUE(IsAtMost(CreateRange(11, 22), &value)); |
| 341 | EXPECT_EQ(22, value); |
| 342 | EXPECT_TRUE(IsAtLeast(CreateRange(11, 22), &value)); |
| 343 | EXPECT_EQ(11, value); |
| 344 | // Symbolic. |
| 345 | EXPECT_FALSE(IsExact(CreateFetch(x_), &value)); |
| 346 | EXPECT_FALSE(IsAtMost(CreateFetch(x_), &value)); |
| 347 | EXPECT_FALSE(IsAtLeast(CreateFetch(x_), &value)); |
| 348 | } |
| 349 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 350 | TEST_F(InductionVarRangeTest, TripCountProperties) { |
| 351 | EXPECT_FALSE(NeedsTripCount(nullptr)); |
| 352 | EXPECT_FALSE(NeedsTripCount(CreateConst(1))); |
| 353 | EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1))); |
| 354 | EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3))); |
| 355 | EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1)))); |
| 356 | |
| 357 | EXPECT_FALSE(IsBodyTripCount(nullptr)); |
| 358 | EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true))); |
| 359 | EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false))); |
| 360 | EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true))); |
| 361 | EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false))); |
| 362 | |
| 363 | EXPECT_FALSE(IsUnsafeTripCount(nullptr)); |
| 364 | EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true))); |
| 365 | EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false))); |
| 366 | EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true))); |
| 367 | EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false))); |
| 368 | } |
| 369 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 370 | TEST_F(InductionVarRangeTest, GetMinMaxNull) { |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 371 | ExpectEqual(Value(), GetMin(nullptr, nullptr)); |
| 372 | ExpectEqual(Value(), GetMax(nullptr, nullptr)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 373 | } |
| 374 | |
| 375 | TEST_F(InductionVarRangeTest, GetMinMaxAdd) { |
| 376 | ExpectEqual(Value(12), |
| 377 | GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 378 | ExpectEqual(Value(22), |
| 379 | GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 380 | ExpectEqual(Value(x_, 1, -20), |
| 381 | GetMin(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); |
| 382 | ExpectEqual(Value(x_, 1, -10), |
| 383 | GetMax(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); |
| 384 | ExpectEqual(Value(x_, 1, 10), |
| 385 | GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); |
| 386 | ExpectEqual(Value(x_, 1, 20), |
| 387 | GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 388 | ExpectEqual(Value(5), |
| 389 | GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); |
| 390 | ExpectEqual(Value(19), |
| 391 | GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); |
| 392 | } |
| 393 | |
| 394 | TEST_F(InductionVarRangeTest, GetMinMaxSub) { |
| 395 | ExpectEqual(Value(-18), |
| 396 | GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 397 | ExpectEqual(Value(-8), |
| 398 | GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 399 | ExpectEqual(Value(x_, 1, 10), |
| 400 | GetMin(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); |
| 401 | ExpectEqual(Value(x_, 1, 20), |
| 402 | GetMax(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); |
| 403 | ExpectEqual(Value(x_, -1, 10), |
| 404 | GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); |
| 405 | ExpectEqual(Value(x_, -1, 20), |
| 406 | GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 407 | ExpectEqual(Value(-25), |
| 408 | GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); |
| 409 | ExpectEqual(Value(-11), |
| 410 | GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); |
| 411 | } |
| 412 | |
| 413 | TEST_F(InductionVarRangeTest, GetMinMaxNeg) { |
| 414 | ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); |
| 415 | ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); |
| 416 | ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); |
| 417 | ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 418 | ExpectEqual(Value(x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); |
| 419 | ExpectEqual(Value(x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 420 | } |
| 421 | |
| 422 | TEST_F(InductionVarRangeTest, GetMinMaxMul) { |
| 423 | ExpectEqual(Value(20), |
| 424 | GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 425 | ExpectEqual(Value(40), |
| 426 | GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 427 | } |
| 428 | |
| 429 | TEST_F(InductionVarRangeTest, GetMinMaxDiv) { |
| 430 | ExpectEqual(Value(3), |
| 431 | GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); |
| 432 | ExpectEqual(Value(5), |
| 433 | GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); |
| 434 | } |
| 435 | |
| 436 | TEST_F(InductionVarRangeTest, GetMinMaxConstant) { |
| 437 | ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr)); |
| 438 | ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr)); |
| 439 | } |
| 440 | |
| 441 | TEST_F(InductionVarRangeTest, GetMinMaxFetch) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 442 | ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(x_), nullptr)); |
| 443 | ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(x_), nullptr)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 444 | } |
| 445 | |
| 446 | TEST_F(InductionVarRangeTest, GetMinMaxLinear) { |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 447 | ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100, true, true))); |
| 448 | ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100, true, true))); |
| 449 | ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100, true, true))); |
| 450 | ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100, true, true))); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 451 | } |
| 452 | |
| 453 | TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) { |
| 454 | ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr)); |
| 455 | ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr)); |
| 456 | ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr)); |
| 457 | ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr)); |
| 458 | ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr)); |
| 459 | ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr)); |
| 460 | } |
| 461 | |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 462 | TEST_F(InductionVarRangeTest, GetMinMaxPolynomial) { |
| 463 | ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), nullptr)); |
| 464 | ExpectEqual(Value(), GetMax(CreatePolynomial(3, 5, 7), nullptr)); |
| 465 | ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true))); |
| 466 | ExpectEqual(Value(45), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true))); |
| 467 | ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true))); |
| 468 | ExpectEqual(Value(160), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true))); |
| 469 | ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7), |
| 470 | CreateTripCount(5, true, true))); |
| 471 | ExpectEqual(Value(111), GetMax(CreatePolynomial(11, 13, -7), |
| 472 | CreateTripCount(5, true, true))); |
| 473 | ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7), |
| 474 | CreateTripCount(10, true, true))); |
| 475 | ExpectEqual(Value(506), GetMax(CreatePolynomial(11, 13, -7), |
| 476 | CreateTripCount(10, true, true))); |
| 477 | ExpectEqual(Value(), GetMin(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true))); |
| 478 | ExpectEqual(Value(), GetMax(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true))); |
| 479 | ExpectEqual(Value(), GetMin(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true))); |
| 480 | ExpectEqual(Value(), GetMax(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true))); |
| 481 | } |
| 482 | |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 483 | TEST_F(InductionVarRangeTest, GetMinMaxGeometricMul) { |
| 484 | ExpectEqual(Value(), GetMin(CreateGeometric(1, 1, 1, '*'), nullptr)); |
| 485 | ExpectEqual(Value(), GetMax(CreateGeometric(1, 1, 1, '*'), nullptr)); |
| 486 | } |
| 487 | |
| 488 | TEST_F(InductionVarRangeTest, GetMinMaxGeometricDiv) { |
| 489 | ExpectEqual(Value(5), GetMin(CreateGeometric(11, 5, 3, '/'), nullptr)); |
| 490 | ExpectEqual(Value(16), GetMax(CreateGeometric(11, 5, 3, '/'), nullptr)); |
| 491 | ExpectEqual(Value(-5), GetMin(CreateGeometric(11, -5, 3, '/'), nullptr)); |
| 492 | ExpectEqual(Value(6), GetMax(CreateGeometric(11, -5, 3, '/'), nullptr)); |
| 493 | ExpectEqual(Value(-6), GetMin(CreateGeometric(-11, 5, 3, '/'), nullptr)); |
| 494 | ExpectEqual(Value(5), GetMax(CreateGeometric(-11, 5, 3, '/'), nullptr)); |
| 495 | ExpectEqual(Value(-16), GetMin(CreateGeometric(-11, -5, 3, '/'), nullptr)); |
| 496 | ExpectEqual(Value(-5), GetMax(CreateGeometric(-11, -5, 3, '/'), nullptr)); |
| 497 | } |
| 498 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 499 | TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) { |
| 500 | ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr)); |
| 501 | ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr)); |
| 502 | } |
| 503 | |
| 504 | TEST_F(InductionVarRangeTest, GetMulMin) { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 505 | ExpectEqual(Value(-14), GetMul(CreateConst(2), CreateRange(-7, 8), true)); |
| 506 | ExpectEqual(Value(-16), GetMul(CreateConst(-2), CreateRange(-7, 8), true)); |
| 507 | ExpectEqual(Value(-14), GetMul(CreateRange(-7, 8), CreateConst(2), true)); |
| 508 | ExpectEqual(Value(-16), GetMul(CreateRange(-7, 8), CreateConst(-2), true)); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 509 | ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true)); |
| 510 | ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 511 | ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true)); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 512 | ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true)); |
| 513 | ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 514 | ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), true)); |
| 515 | ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), true)); |
| 516 | ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), true)); |
| 517 | ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), true)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 518 | } |
| 519 | |
| 520 | TEST_F(InductionVarRangeTest, GetMulMax) { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 521 | ExpectEqual(Value(16), GetMul(CreateConst(2), CreateRange(-7, 8), false)); |
| 522 | ExpectEqual(Value(14), GetMul(CreateConst(-2), CreateRange(-7, 8), false)); |
| 523 | ExpectEqual(Value(16), GetMul(CreateRange(-7, 8), CreateConst(2), false)); |
| 524 | ExpectEqual(Value(14), GetMul(CreateRange(-7, 8), CreateConst(-2), false)); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 525 | ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false)); |
| 526 | ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 527 | ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false)); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 528 | ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false)); |
| 529 | ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 530 | ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), false)); |
| 531 | ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), false)); |
| 532 | ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), false)); |
| 533 | ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), false)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 534 | } |
| 535 | |
| 536 | TEST_F(InductionVarRangeTest, GetDivMin) { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 537 | ExpectEqual(Value(-5), GetDiv(CreateRange(-10, 20), CreateConst(2), true)); |
| 538 | ExpectEqual(Value(-10), GetDiv(CreateRange(-10, 20), CreateConst(-2), true)); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 539 | ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true)); |
| 540 | ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 541 | ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true)); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 542 | ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true)); |
| 543 | ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 544 | ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), true)); |
| 545 | ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), true)); |
| 546 | ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, -40), true)); |
| 547 | ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), true)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 548 | } |
| 549 | |
| 550 | TEST_F(InductionVarRangeTest, GetDivMax) { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 551 | ExpectEqual(Value(10), GetDiv(CreateRange(-10, 20), CreateConst(2), false)); |
| 552 | ExpectEqual(Value(5), GetDiv(CreateRange(-10, 20), CreateConst(-2), false)); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 553 | ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false)); |
| 554 | ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 555 | ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false)); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 556 | ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false)); |
| 557 | ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false)); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 558 | ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), false)); |
| 559 | ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), false)); |
| 560 | ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, 40), false)); |
| 561 | ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 562 | } |
| 563 | |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 564 | TEST_F(InductionVarRangeTest, GetMinMaxRem) { |
| 565 | ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 566 | ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 567 | ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr)); |
| 568 | ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr)); |
| 569 | ExpectEqual(Value(2), GetMin(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr)); |
| 570 | ExpectEqual(Value(2), GetMax(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr)); |
| 571 | ExpectEqual(Value(1), GetMin(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr)); |
| 572 | ExpectEqual(Value(1), GetMax(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr)); |
| 573 | } |
| 574 | |
| 575 | TEST_F(InductionVarRangeTest, GetRem) { |
| 576 | ExpectEqual(Value(0), GetRem(CreateConst(1), CreateConst(1))); |
| 577 | ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(5))); |
| 578 | ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(5))); |
| 579 | ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(5))); |
| 580 | ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(5))); |
| 581 | ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(-5))); |
| 582 | ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(-5))); |
| 583 | ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(-5))); |
| 584 | ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(-5))); |
| 585 | ExpectEqual(Value(), GetRem(CreateConst(1), CreateConst(0))); |
| 586 | } |
| 587 | |
| 588 | TEST_F(InductionVarRangeTest, GetMinMaxXor) { |
| 589 | ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 590 | ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr)); |
| 591 | ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr)); |
| 592 | ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr)); |
| 593 | ExpectEqual(Value(3), GetMin(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr)); |
| 594 | ExpectEqual(Value(3), GetMax(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr)); |
| 595 | } |
| 596 | |
| 597 | TEST_F(InductionVarRangeTest, GetXor) { |
| 598 | ExpectEqual(Value(0), GetXor(CreateConst(1), CreateConst(1))); |
| 599 | ExpectEqual(Value(3), GetXor(CreateConst(1), CreateConst(2))); |
| 600 | ExpectEqual(Value(-2), GetXor(CreateConst(1), CreateConst(-1))); |
| 601 | ExpectEqual(Value(0), GetXor(CreateConst(-1), CreateConst(-1))); |
| 602 | } |
| 603 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 604 | TEST_F(InductionVarRangeTest, AddValue) { |
| 605 | ExpectEqual(Value(110), AddValue(Value(10), Value(100))); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 606 | ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1))); |
| 607 | ExpectEqual(Value(x_, 3, -5), AddValue(Value(x_, 2, -4), Value(x_, 1, -1))); |
| 608 | ExpectEqual(Value(), AddValue(Value(x_, 1, 5), Value(y_, 1, -7))); |
| 609 | ExpectEqual(Value(x_, 1, 23), AddValue(Value(x_, 1, 20), Value(3))); |
| 610 | ExpectEqual(Value(y_, 1, 5), AddValue(Value(55), Value(y_, 1, -50))); |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 611 | const int32_t max_value = std::numeric_limits<int32_t>::max(); |
| 612 | ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5))); |
| 613 | ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 614 | } |
| 615 | |
| 616 | TEST_F(InductionVarRangeTest, SubValue) { |
| 617 | ExpectEqual(Value(-90), SubValue(Value(10), Value(100))); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 618 | ExpectEqual(Value(-3), SubValue(Value(x_, 1, -4), Value(x_, 1, -1))); |
| 619 | ExpectEqual(Value(x_, 2, -3), SubValue(Value(x_, 3, -4), Value(x_, 1, -1))); |
| 620 | ExpectEqual(Value(), SubValue(Value(x_, 1, 5), Value(y_, 1, -7))); |
| 621 | ExpectEqual(Value(x_, 1, 17), SubValue(Value(x_, 1, 20), Value(3))); |
| 622 | ExpectEqual(Value(y_, -4, 105), SubValue(Value(55), Value(y_, 4, -50))); |
Aart Bik | cd26feb | 2015-09-23 17:50:50 -0700 | [diff] [blame] | 623 | const int32_t min_value = std::numeric_limits<int32_t>::min(); |
| 624 | ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5))); |
| 625 | ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 626 | } |
| 627 | |
| 628 | TEST_F(InductionVarRangeTest, MulValue) { |
| 629 | ExpectEqual(Value(1000), MulValue(Value(10), Value(100))); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 630 | ExpectEqual(Value(), MulValue(Value(x_, 1, -4), Value(x_, 1, -1))); |
| 631 | ExpectEqual(Value(), MulValue(Value(x_, 1, 5), Value(y_, 1, -7))); |
| 632 | ExpectEqual(Value(x_, 9, 60), MulValue(Value(x_, 3, 20), Value(3))); |
| 633 | ExpectEqual(Value(y_, 55, -110), MulValue(Value(55), Value(y_, 1, -2))); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 634 | ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 635 | } |
| 636 | |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 637 | TEST_F(InductionVarRangeTest, MulValueSpecial) { |
| 638 | const int32_t min_value = std::numeric_limits<int32_t>::min(); |
| 639 | const int32_t max_value = std::numeric_limits<int32_t>::max(); |
| 640 | |
| 641 | // Unsafe. |
| 642 | ExpectEqual(Value(), MulValue(Value(min_value), Value(min_value))); |
| 643 | ExpectEqual(Value(), MulValue(Value(min_value), Value(-1))); |
| 644 | ExpectEqual(Value(), MulValue(Value(min_value), Value(max_value))); |
| 645 | ExpectEqual(Value(), MulValue(Value(max_value), Value(max_value))); |
| 646 | |
| 647 | // Safe. |
| 648 | ExpectEqual(Value(min_value), MulValue(Value(min_value), Value(1))); |
| 649 | ExpectEqual(Value(max_value), MulValue(Value(max_value), Value(1))); |
| 650 | ExpectEqual(Value(-max_value), MulValue(Value(max_value), Value(-1))); |
| 651 | ExpectEqual(Value(-1), MulValue(Value(1), Value(-1))); |
| 652 | ExpectEqual(Value(1), MulValue(Value(-1), Value(-1))); |
| 653 | } |
| 654 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 655 | TEST_F(InductionVarRangeTest, DivValue) { |
| 656 | ExpectEqual(Value(25), DivValue(Value(100), Value(4))); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 657 | ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1))); |
| 658 | ExpectEqual(Value(), DivValue(Value(x_, 1, 5), Value(y_, 1, -7))); |
| 659 | ExpectEqual(Value(), DivValue(Value(x_, 12, 24), Value(3))); |
| 660 | ExpectEqual(Value(), DivValue(Value(55), Value(y_, 1, -50))); |
Aart Bik | b3365e0 | 2015-09-21 14:45:05 -0700 | [diff] [blame] | 661 | ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 662 | } |
| 663 | |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 664 | TEST_F(InductionVarRangeTest, DivValueSpecial) { |
| 665 | const int32_t min_value = std::numeric_limits<int32_t>::min(); |
| 666 | const int32_t max_value = std::numeric_limits<int32_t>::max(); |
| 667 | |
| 668 | // Unsafe. |
| 669 | ExpectEqual(Value(), DivValue(Value(min_value), Value(-1))); |
| 670 | |
| 671 | // Safe. |
| 672 | ExpectEqual(Value(1), DivValue(Value(min_value), Value(min_value))); |
| 673 | ExpectEqual(Value(1), DivValue(Value(max_value), Value(max_value))); |
| 674 | ExpectEqual(Value(min_value), DivValue(Value(min_value), Value(1))); |
| 675 | ExpectEqual(Value(max_value), DivValue(Value(max_value), Value(1))); |
| 676 | ExpectEqual(Value(-max_value), DivValue(Value(max_value), Value(-1))); |
| 677 | ExpectEqual(Value(-1), DivValue(Value(1), Value(-1))); |
| 678 | ExpectEqual(Value(1), DivValue(Value(-1), Value(-1))); |
| 679 | } |
| 680 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 681 | TEST_F(InductionVarRangeTest, MinValue) { |
| 682 | ExpectEqual(Value(10), MinValue(Value(10), Value(100))); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 683 | ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1))); |
| 684 | ExpectEqual(Value(x_, 4, -4), MinValue(Value(x_, 4, -4), Value(x_, 4, -1))); |
| 685 | ExpectEqual(Value(), MinValue(Value(x_, 1, 5), Value(y_, 1, -7))); |
| 686 | ExpectEqual(Value(), MinValue(Value(x_, 1, 20), Value(3))); |
| 687 | ExpectEqual(Value(), MinValue(Value(55), Value(y_, 1, -50))); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 688 | } |
| 689 | |
| 690 | TEST_F(InductionVarRangeTest, MaxValue) { |
| 691 | ExpectEqual(Value(100), MaxValue(Value(10), Value(100))); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 692 | ExpectEqual(Value(x_, 1, -1), MaxValue(Value(x_, 1, -4), Value(x_, 1, -1))); |
| 693 | ExpectEqual(Value(x_, 4, -1), MaxValue(Value(x_, 4, -4), Value(x_, 4, -1))); |
| 694 | ExpectEqual(Value(), MaxValue(Value(x_, 1, 5), Value(y_, 1, -7))); |
| 695 | ExpectEqual(Value(), MaxValue(Value(x_, 1, 20), Value(3))); |
| 696 | ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50))); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 697 | } |
| 698 | |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 699 | TEST_F(InductionVarRangeTest, ArrayLengthAndHints) { |
| 700 | HInstruction* new_array = new (&allocator_) |
| 701 | HNewArray(x_, |
| 702 | graph_->GetCurrentMethod(), |
Andreas Gampe | a5b09a6 | 2016-11-17 15:21:22 -0800 | [diff] [blame] | 703 | 0, |
| 704 | dex::TypeIndex(Primitive::kPrimInt), |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 705 | graph_->GetDexFile(), |
| 706 | kQuickAllocArray); |
| 707 | entry_block_->AddInstruction(new_array); |
| 708 | HInstruction* array_length = new (&allocator_) HArrayLength(new_array, 0); |
| 709 | entry_block_->AddInstruction(array_length); |
| 710 | // With null hint: yields extreme constants. |
| 711 | const int32_t max_value = std::numeric_limits<int32_t>::max(); |
| 712 | SetHint(nullptr); |
| 713 | ExpectEqual(Value(0), GetMin(CreateFetch(array_length), nullptr)); |
| 714 | ExpectEqual(Value(max_value), GetMax(CreateFetch(array_length), nullptr)); |
| 715 | // With explicit hint: yields the length instruction. |
| 716 | SetHint(array_length); |
| 717 | ExpectEqual(Value(array_length, 1, 0), GetMin(CreateFetch(array_length), nullptr)); |
| 718 | ExpectEqual(Value(array_length, 1, 0), GetMax(CreateFetch(array_length), nullptr)); |
| 719 | // With any non-null hint: chases beyond the length instruction. |
| 720 | SetHint(x_); |
| 721 | ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(array_length), nullptr)); |
| 722 | ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(array_length), nullptr)); |
| 723 | } |
| 724 | |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 725 | // |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 726 | // Tests on public methods. |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 727 | // |
| 728 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 729 | TEST_F(InductionVarRangeTest, ConstantTripCountUp) { |
| 730 | BuildLoop(0, graph_->GetIntConstant(1000), 1); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 731 | PerformInductionVarAnalysis(); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 732 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 733 | Value v1, v2; |
| 734 | bool needs_finite_test = true; |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 735 | bool needs_taken_test = true; |
| 736 | |
| 737 | HInstruction* phi = condition_->InputAt(0); |
| 738 | HInstruction* exit = exit_block_->GetLastInstruction(); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 739 | |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 740 | // In context of header: known. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 741 | range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 742 | EXPECT_FALSE(needs_finite_test); |
| 743 | ExpectEqual(Value(0), v1); |
| 744 | ExpectEqual(Value(1000), v2); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 745 | |
| 746 | // In context of loop-body: known. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 747 | range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 748 | EXPECT_FALSE(needs_finite_test); |
| 749 | ExpectEqual(Value(0), v1); |
| 750 | ExpectEqual(Value(999), v2); |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 751 | range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 752 | EXPECT_FALSE(needs_finite_test); |
| 753 | ExpectEqual(Value(1), v1); |
| 754 | ExpectEqual(Value(1000), v2); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 755 | |
| 756 | // Induction vs. no-induction. |
| 757 | EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); |
| 758 | EXPECT_TRUE(range_.CanGenerateLastValue(phi)); |
| 759 | EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test)); |
| 760 | EXPECT_FALSE(range_.CanGenerateLastValue(exit)); |
| 761 | |
| 762 | // Last value (unsimplified). |
| 763 | HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_); |
| 764 | ASSERT_TRUE(last->IsAdd()); |
| 765 | ASSERT_TRUE(last->InputAt(0)->IsIntConstant()); |
| 766 | EXPECT_EQ(1000, last->InputAt(0)->AsIntConstant()->GetValue()); |
| 767 | ASSERT_TRUE(last->InputAt(1)->IsIntConstant()); |
| 768 | EXPECT_EQ(0, last->InputAt(1)->AsIntConstant()->GetValue()); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 769 | } |
| 770 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 771 | TEST_F(InductionVarRangeTest, ConstantTripCountDown) { |
| 772 | BuildLoop(1000, graph_->GetIntConstant(0), -1); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 773 | PerformInductionVarAnalysis(); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 774 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 775 | Value v1, v2; |
| 776 | bool needs_finite_test = true; |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 777 | bool needs_taken_test = true; |
| 778 | |
| 779 | HInstruction* phi = condition_->InputAt(0); |
| 780 | HInstruction* exit = exit_block_->GetLastInstruction(); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 781 | |
| 782 | // In context of header: known. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 783 | range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 784 | EXPECT_FALSE(needs_finite_test); |
| 785 | ExpectEqual(Value(0), v1); |
| 786 | ExpectEqual(Value(1000), v2); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 787 | |
| 788 | // In context of loop-body: known. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 789 | range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 790 | EXPECT_FALSE(needs_finite_test); |
| 791 | ExpectEqual(Value(1), v1); |
| 792 | ExpectEqual(Value(1000), v2); |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 793 | range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 794 | EXPECT_FALSE(needs_finite_test); |
| 795 | ExpectEqual(Value(0), v1); |
| 796 | ExpectEqual(Value(999), v2); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 797 | |
| 798 | // Induction vs. no-induction. |
| 799 | EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); |
| 800 | EXPECT_TRUE(range_.CanGenerateLastValue(phi)); |
| 801 | EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test)); |
| 802 | EXPECT_FALSE(range_.CanGenerateLastValue(exit)); |
| 803 | |
| 804 | // Last value (unsimplified). |
| 805 | HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_); |
| 806 | ASSERT_TRUE(last->IsSub()); |
| 807 | ASSERT_TRUE(last->InputAt(0)->IsIntConstant()); |
| 808 | EXPECT_EQ(1000, last->InputAt(0)->AsIntConstant()->GetValue()); |
| 809 | ASSERT_TRUE(last->InputAt(1)->IsNeg()); |
| 810 | last = last->InputAt(1)->InputAt(0); |
| 811 | ASSERT_TRUE(last->IsSub()); |
| 812 | ASSERT_TRUE(last->InputAt(0)->IsIntConstant()); |
| 813 | EXPECT_EQ(0, last->InputAt(0)->AsIntConstant()->GetValue()); |
| 814 | ASSERT_TRUE(last->InputAt(1)->IsIntConstant()); |
| 815 | EXPECT_EQ(1000, last->InputAt(1)->AsIntConstant()->GetValue()); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 816 | } |
| 817 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 818 | TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 819 | BuildLoop(0, x_, 1); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 820 | PerformInductionVarAnalysis(); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 821 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 822 | Value v1, v2; |
| 823 | bool needs_finite_test = true; |
| 824 | bool needs_taken_test = true; |
| 825 | |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 826 | HInstruction* phi = condition_->InputAt(0); |
| 827 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 828 | // In context of header: upper unknown. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 829 | range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 830 | EXPECT_FALSE(needs_finite_test); |
| 831 | ExpectEqual(Value(0), v1); |
| 832 | ExpectEqual(Value(), v2); |
| 833 | |
| 834 | // In context of loop-body: known. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 835 | range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 836 | EXPECT_FALSE(needs_finite_test); |
| 837 | ExpectEqual(Value(0), v1); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 838 | ExpectEqual(Value(x_, 1, -1), v2); |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 839 | range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 840 | EXPECT_FALSE(needs_finite_test); |
| 841 | ExpectEqual(Value(1), v1); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 842 | ExpectEqual(Value(x_, 1, 0), v2); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 843 | |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 844 | HInstruction* lower = nullptr; |
| 845 | HInstruction* upper = nullptr; |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 846 | |
| 847 | // Can generate code in context of loop-body only. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 848 | EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test)); |
| 849 | ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 850 | EXPECT_FALSE(needs_finite_test); |
| 851 | EXPECT_TRUE(needs_taken_test); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 852 | |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 853 | // Generates code (unsimplified). |
| 854 | range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 855 | |
| 856 | // Verify lower is 0+0. |
| 857 | ASSERT_TRUE(lower != nullptr); |
| 858 | ASSERT_TRUE(lower->IsAdd()); |
| 859 | ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); |
| 860 | EXPECT_EQ(0, lower->InputAt(0)->AsIntConstant()->GetValue()); |
| 861 | ASSERT_TRUE(lower->InputAt(1)->IsIntConstant()); |
| 862 | EXPECT_EQ(0, lower->InputAt(1)->AsIntConstant()->GetValue()); |
| 863 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 864 | // Verify upper is (V-1)+0. |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 865 | ASSERT_TRUE(upper != nullptr); |
| 866 | ASSERT_TRUE(upper->IsAdd()); |
| 867 | ASSERT_TRUE(upper->InputAt(0)->IsSub()); |
| 868 | EXPECT_TRUE(upper->InputAt(0)->InputAt(0)->IsParameterValue()); |
| 869 | ASSERT_TRUE(upper->InputAt(0)->InputAt(1)->IsIntConstant()); |
| 870 | EXPECT_EQ(1, upper->InputAt(0)->InputAt(1)->AsIntConstant()->GetValue()); |
| 871 | ASSERT_TRUE(upper->InputAt(1)->IsIntConstant()); |
| 872 | EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue()); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 873 | |
| 874 | // Verify taken-test is 0<V. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 875 | HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 876 | ASSERT_TRUE(taken != nullptr); |
| 877 | ASSERT_TRUE(taken->IsLessThan()); |
| 878 | ASSERT_TRUE(taken->InputAt(0)->IsIntConstant()); |
| 879 | EXPECT_EQ(0, taken->InputAt(0)->AsIntConstant()->GetValue()); |
| 880 | EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 881 | |
| 882 | // Replacement. |
| 883 | range_.Replace(loop_header_->GetLastInstruction(), x_, y_); |
| 884 | range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); |
| 885 | EXPECT_FALSE(needs_finite_test); |
| 886 | ExpectEqual(Value(1), v1); |
| 887 | ExpectEqual(Value(y_, 1, 0), v2); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 888 | } |
| 889 | |
| 890 | TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 891 | BuildLoop(1000, x_, -1); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 892 | PerformInductionVarAnalysis(); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 893 | |
| 894 | Value v1, v2; |
| 895 | bool needs_finite_test = true; |
| 896 | bool needs_taken_test = true; |
| 897 | |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 898 | HInstruction* phi = condition_->InputAt(0); |
| 899 | |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 900 | // In context of header: lower unknown. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 901 | range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 902 | EXPECT_FALSE(needs_finite_test); |
| 903 | ExpectEqual(Value(), v1); |
| 904 | ExpectEqual(Value(1000), v2); |
| 905 | |
| 906 | // In context of loop-body: known. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 907 | range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 908 | EXPECT_FALSE(needs_finite_test); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 909 | ExpectEqual(Value(x_, 1, 1), v1); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 910 | ExpectEqual(Value(1000), v2); |
Aart Bik | 52be7e7 | 2016-06-23 11:20:41 -0700 | [diff] [blame] | 911 | range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 912 | EXPECT_FALSE(needs_finite_test); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 913 | ExpectEqual(Value(x_, 1, 0), v1); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 914 | ExpectEqual(Value(999), v2); |
| 915 | |
| 916 | HInstruction* lower = nullptr; |
| 917 | HInstruction* upper = nullptr; |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 918 | |
| 919 | // Can generate code in context of loop-body only. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 920 | EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test)); |
| 921 | ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 922 | EXPECT_FALSE(needs_finite_test); |
| 923 | EXPECT_TRUE(needs_taken_test); |
| 924 | |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 925 | // Generates code (unsimplified). |
| 926 | range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 927 | |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 928 | // Verify lower is 1000-((1000-V)-1). |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 929 | ASSERT_TRUE(lower != nullptr); |
| 930 | ASSERT_TRUE(lower->IsSub()); |
| 931 | ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); |
| 932 | EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue()); |
| 933 | lower = lower->InputAt(1); |
| 934 | ASSERT_TRUE(lower->IsSub()); |
| 935 | ASSERT_TRUE(lower->InputAt(1)->IsIntConstant()); |
| 936 | EXPECT_EQ(1, lower->InputAt(1)->AsIntConstant()->GetValue()); |
| 937 | lower = lower->InputAt(0); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 938 | ASSERT_TRUE(lower->IsSub()); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 939 | ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); |
| 940 | EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue()); |
| 941 | EXPECT_TRUE(lower->InputAt(1)->IsParameterValue()); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 942 | |
| 943 | // Verify upper is 1000-0. |
| 944 | ASSERT_TRUE(upper != nullptr); |
| 945 | ASSERT_TRUE(upper->IsSub()); |
| 946 | ASSERT_TRUE(upper->InputAt(0)->IsIntConstant()); |
| 947 | EXPECT_EQ(1000, upper->InputAt(0)->AsIntConstant()->GetValue()); |
| 948 | ASSERT_TRUE(upper->InputAt(1)->IsIntConstant()); |
| 949 | EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue()); |
| 950 | |
| 951 | // Verify taken-test is 1000>V. |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 952 | HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_); |
Aart Bik | 389b3db | 2015-10-28 14:23:40 -0700 | [diff] [blame] | 953 | ASSERT_TRUE(taken != nullptr); |
| 954 | ASSERT_TRUE(taken->IsGreaterThan()); |
| 955 | ASSERT_TRUE(taken->InputAt(0)->IsIntConstant()); |
| 956 | EXPECT_EQ(1000, taken->InputAt(0)->AsIntConstant()->GetValue()); |
| 957 | EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); |
Aart Bik | 16d3a65 | 2016-09-09 10:33:50 -0700 | [diff] [blame] | 958 | |
| 959 | // Replacement. |
| 960 | range_.Replace(loop_header_->GetLastInstruction(), x_, y_); |
| 961 | range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); |
| 962 | EXPECT_FALSE(needs_finite_test); |
| 963 | ExpectEqual(Value(y_, 1, 0), v1); |
| 964 | ExpectEqual(Value(999), v2); |
Aart Bik | aec3cce | 2015-10-14 17:44:55 -0700 | [diff] [blame] | 965 | } |
| 966 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 967 | } // namespace art |