130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik/* 230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * Copyright (C) 2015 The Android Open Source Project 330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * 430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * Licensed under the Apache License, Version 2.0 (the "License"); 530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * you may not use this file except in compliance with the License. 630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * You may obtain a copy of the License at 730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * 830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * http://www.apache.org/licenses/LICENSE-2.0 930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * 1030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * Unless required by applicable law or agreed to in writing, software 1130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * distributed under the License is distributed on an "AS IS" BASIS, 1230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * See the License for the specific language governing permissions and 1430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * limitations under the License. 1530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik */ 1630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 1730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#include <regex> 1830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 1930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#include "base/arena_allocator.h" 2030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#include "builder.h" 2130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#include "induction_var_analysis.h" 2230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#include "nodes.h" 2330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik#include "optimizing_unit_test.h" 2430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Biknamespace art { 2630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik/** 2830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik * Fixture class for the InductionVarAnalysis tests. 2930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik */ 304833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilclass InductionVarAnalysisTest : public CommonCompilerTest { 3130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik public: 3230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionVarAnalysisTest() : pool_(), allocator_(&pool_) { 3330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_ = CreateGraph(&allocator_); 3430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 3530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 3630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ~InductionVarAnalysisTest() { } 3730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 3830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Builds single for-loop at depth d. 3930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void BuildForLoop(int d, int n) { 4030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ASSERT_LT(d, n); 4130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_preheader_[d] = new (&allocator_) HBasicBlock(graph_); 4230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->AddBlock(loop_preheader_[d]); 4330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_header_[d] = new (&allocator_) HBasicBlock(graph_); 4430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->AddBlock(loop_header_[d]); 4530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_preheader_[d]->AddSuccessor(loop_header_[d]); 4630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (d < (n - 1)) { 4730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildForLoop(d + 1, n); 4830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 4930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_body_[d] = new (&allocator_) HBasicBlock(graph_); 5030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->AddBlock(loop_body_[d]); 5130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_body_[d]->AddSuccessor(loop_header_[d]); 5230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (d < (n - 1)) { 5330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_header_[d]->AddSuccessor(loop_preheader_[d + 1]); 5430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_header_[d + 1]->AddSuccessor(loop_body_[d]); 5530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else { 5630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_header_[d]->AddSuccessor(loop_body_[d]); 5730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 5830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 5930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 6030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Builds a n-nested loop in CFG where each loop at depth 0 <= d < n 6130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // is defined as "for (int i_d = 0; i_d < 100; i_d++)". Tests can further 6230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // populate the loop with instructions to set up interesting scenarios. 6330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void BuildLoopNest(int n) { 6430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ASSERT_LE(n, 10); 65e609b7cf9996389e6e693f149489737436172a2cAart Bik graph_->SetNumberOfVRegs(n + 3); 6630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 6730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Build basic blocks with entry, nested loop, exit. 6830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik entry_ = new (&allocator_) HBasicBlock(graph_); 6930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->AddBlock(entry_); 7030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildForLoop(0, n); 71db51efb3617d15f1cd9e5ff0cc2d934777014e9aDavid Brazdil return_ = new (&allocator_) HBasicBlock(graph_); 72db51efb3617d15f1cd9e5ff0cc2d934777014e9aDavid Brazdil graph_->AddBlock(return_); 7330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik exit_ = new (&allocator_) HBasicBlock(graph_); 7430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->AddBlock(exit_); 7530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik entry_->AddSuccessor(loop_preheader_[0]); 76db51efb3617d15f1cd9e5ff0cc2d934777014e9aDavid Brazdil loop_header_[0]->AddSuccessor(return_); 77db51efb3617d15f1cd9e5ff0cc2d934777014e9aDavid Brazdil return_->AddSuccessor(exit_); 7830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->SetEntryBlock(entry_); 7930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->SetExitBlock(exit_); 8030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 8130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Provide entry and exit instructions. 82e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle parameter_ = new (&allocator_) HParameterValue( 83e6e3beaf2d35d18a79f5e7b60a21e75fac9fd15dCalin Juravle graph_->GetDexFile(), 0, 0, Primitive::kPrimNot, true); 8430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik entry_->AddInstruction(parameter_); 85e609b7cf9996389e6e693f149489737436172a2cAart Bik constant0_ = graph_->GetIntConstant(0); 86e609b7cf9996389e6e693f149489737436172a2cAart Bik constant1_ = graph_->GetIntConstant(1); 87e609b7cf9996389e6e693f149489737436172a2cAart Bik constant100_ = graph_->GetIntConstant(100); 8815693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil float_constant0_ = graph_->GetFloatConstant(0.0f); 89db51efb3617d15f1cd9e5ff0cc2d934777014e9aDavid Brazdil return_->AddInstruction(new (&allocator_) HReturnVoid()); 90e609b7cf9996389e6e693f149489737436172a2cAart Bik exit_->AddInstruction(new (&allocator_) HExit()); 9130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 9230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Provide loop instructions. 9330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik for (int d = 0; d < n; d++) { 94badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil basic_[d] = new (&allocator_) HPhi(&allocator_, d, 0, Primitive::kPrimInt); 954833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil loop_preheader_[d]->AddInstruction(new (&allocator_) HGoto()); 96badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil loop_header_[d]->AddPhi(basic_[d]); 97badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* compare = new (&allocator_) HLessThan(basic_[d], constant100_); 9830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_header_[d]->AddInstruction(compare); 9930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_header_[d]->AddInstruction(new (&allocator_) HIf(compare)); 100badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil increment_[d] = new (&allocator_) HAdd(Primitive::kPrimInt, basic_[d], constant1_); 10130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_body_[d]->AddInstruction(increment_[d]); 10230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_body_[d]->AddInstruction(new (&allocator_) HGoto()); 103badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 104badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil basic_[d]->AddInput(constant0_); 105badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil basic_[d]->AddInput(increment_[d]); 10630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 10730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 10830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 10930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Builds if-statement at depth d. 110badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock **ifF) { 11130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* cond = new (&allocator_) HBasicBlock(graph_); 11230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* ifTrue = new (&allocator_) HBasicBlock(graph_); 11330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* ifFalse = new (&allocator_) HBasicBlock(graph_); 11430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->AddBlock(cond); 11530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->AddBlock(ifTrue); 11630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik graph_->AddBlock(ifFalse); 11730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Conditional split. 11830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_header_[d]->ReplaceSuccessor(loop_body_[d], cond); 11930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik cond->AddSuccessor(ifTrue); 12030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik cond->AddSuccessor(ifFalse); 12130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ifTrue->AddSuccessor(loop_body_[d]); 12230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ifFalse->AddSuccessor(loop_body_[d]); 12330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik cond->AddInstruction(new (&allocator_) HIf(parameter_)); 12430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik *ifT = ifTrue; 12530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik *ifF = ifFalse; 126badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 127badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* select_phi = new (&allocator_) HPhi(&allocator_, -1, 0, Primitive::kPrimInt); 128badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil loop_body_[d]->AddPhi(select_phi); 129badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil return select_phi; 13030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 13130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 13230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Inserts instruction right before increment at depth d. 13330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* InsertInstruction(HInstruction* instruction, int d) { 13430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_body_[d]->InsertInstructionBefore(instruction, increment_[d]); 13530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return instruction; 13630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 13730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 138badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil // Inserts a phi to loop header at depth d and returns it. 139badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* InsertLoopPhi(int vreg, int d) { 140badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* phi = new (&allocator_) HPhi(&allocator_, vreg, 0, Primitive::kPrimInt); 141badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil loop_header_[d]->AddPhi(phi); 142badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil return phi; 14330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 14430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 145badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil // Inserts an array store with given `subscript` at depth d to 14630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // enable tests to inspect the computed induction at that point easily. 147badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* InsertArrayStore(HInstruction* subscript, int d) { 14815693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // ArraySet is given a float value in order to avoid SsaBuilder typing 14915693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // it from the array's non-existent reference type info. 15030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return InsertInstruction(new (&allocator_) HArraySet( 151badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil parameter_, subscript, float_constant0_, Primitive::kPrimFloat, 0), d); 15230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 15330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 154e609b7cf9996389e6e693f149489737436172a2cAart Bik // Returns induction information of instruction in loop at depth d. 155e609b7cf9996389e6e693f149489737436172a2cAart Bik std::string GetInductionInfo(HInstruction* instruction, int d) { 156e609b7cf9996389e6e693f149489737436172a2cAart Bik return HInductionVarAnalysis::InductionToString( 157e609b7cf9996389e6e693f149489737436172a2cAart Bik iva_->LookupInfo(loop_body_[d]->GetLoopInformation(), instruction)); 15830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 15930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 1607829691e27c528ca52753dd98bcb4785e328388aAart Bik // Returns true if instructions have identical induction. 1617829691e27c528ca52753dd98bcb4785e328388aAart Bik bool HaveSameInduction(HInstruction* instruction1, HInstruction* instruction2) { 1627829691e27c528ca52753dd98bcb4785e328388aAart Bik return HInductionVarAnalysis::InductionEqual( 1637829691e27c528ca52753dd98bcb4785e328388aAart Bik iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction1), 1647829691e27c528ca52753dd98bcb4785e328388aAart Bik iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction2)); 1657829691e27c528ca52753dd98bcb4785e328388aAart Bik } 1667829691e27c528ca52753dd98bcb4785e328388aAart Bik 16730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Performs InductionVarAnalysis (after proper set up). 16830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik void PerformInductionVarAnalysis() { 169badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil graph_->BuildDominatorTree(); 17030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik iva_ = new (&allocator_) HInductionVarAnalysis(graph_); 17130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik iva_->Run(); 17230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 17330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 17430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // General building fields. 17530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ArenaPool pool_; 17630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ArenaAllocator allocator_; 17730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HGraph* graph_; 17830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInductionVarAnalysis* iva_; 17930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 18030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Fixed basic blocks and instructions. 18130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* entry_; 182db51efb3617d15f1cd9e5ff0cc2d934777014e9aDavid Brazdil HBasicBlock* return_; 18330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* exit_; 18430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* parameter_; // "this" 18530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* constant0_; 18630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* constant1_; 18730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* constant100_; 18815693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil HInstruction* float_constant0_; 18930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 19030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Loop specifics. 19130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* loop_preheader_[10]; 19230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* loop_header_[10]; 19330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* loop_body_[10]; 19430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* increment_[10]; 195badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* basic_[10]; // "vreg_d", the "i_d" 19630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik}; 19730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 19830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik// 19930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik// The actual InductionVarAnalysis tests. 20030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik// 20130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 20230efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikTEST_F(InductionVarAnalysisTest, ProperLoopSetup) { 20330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Setup: 20430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i_0 = 0; i_0 < 100; i_0++) { 20530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // .. 20630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i_9 = 0; i_9 < 100; i_9++) { 20730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 20830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // .. 20930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 21030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildLoopNest(10); 211badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil graph_->BuildDominatorTree(); 2120d345cf8db01f40db250f80de5104e0df24234faAart Bik 21330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ASSERT_EQ(entry_->GetLoopInformation(), nullptr); 21430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik for (int d = 0; d < 1; d++) { 21530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(), 21630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik (d == 0) ? nullptr 21730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik : loop_header_[d - 1]->GetLoopInformation()); 21830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ASSERT_NE(loop_header_[d]->GetLoopInformation(), nullptr); 21930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ASSERT_NE(loop_body_[d]->GetLoopInformation(), nullptr); 22030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ASSERT_EQ(loop_header_[d]->GetLoopInformation(), 22130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik loop_body_[d]->GetLoopInformation()); 22230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 22330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ASSERT_EQ(exit_->GetLoopInformation(), nullptr); 22430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 22530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 226e609b7cf9996389e6e693f149489737436172a2cAart BikTEST_F(InductionVarAnalysisTest, FindBasicInduction) { 22730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Setup: 22830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i = 0; i < 100; i++) { 229e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[i] = 0; 23030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 23130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildLoopNest(1); 23230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* store = InsertArrayStore(basic_[0], 0); 23330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik PerformInductionVarAnalysis(); 23430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2350d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + (0)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str()); 2360d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(increment_[0], 0).c_str()); 237d14c59564870c910bdc823081f0ed1101f599231Aart Bik 2387829691e27c528ca52753dd98bcb4785e328388aAart Bik // Offset matters! 2397829691e27c528ca52753dd98bcb4785e328388aAart Bik EXPECT_FALSE(HaveSameInduction(store->InputAt(1), increment_[0])); 2407829691e27c528ca52753dd98bcb4785e328388aAart Bik 241d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Trip-count. 24222f058726d35dd8f40b3763649e61740b3d22535Aart Bik EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", 2439401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 24430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 24530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 246e609b7cf9996389e6e693f149489737436172a2cAart BikTEST_F(InductionVarAnalysisTest, FindDerivedInduction) { 24730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Setup: 24830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i = 0; i < 100; i++) { 249e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 100 + i; 250e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 100 - i; 251e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 100 * i; 252e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = i << 1; 253e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = - i; 25430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 25530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildLoopNest(1); 25630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction *add = InsertInstruction( 257badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HAdd(Primitive::kPrimInt, constant100_, basic_[0]), 0); 25830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction *sub = InsertInstruction( 259badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0); 26030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction *mul = InsertInstruction( 261badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HMul(Primitive::kPrimInt, constant100_, basic_[0]), 0); 262e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *shl = InsertInstruction( 263badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0); 26430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction *neg = InsertInstruction( 265badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HNeg(Primitive::kPrimInt, basic_[0]), 0); 26630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik PerformInductionVarAnalysis(); 26730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2680d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + (100)):PrimInt", GetInductionInfo(add, 0).c_str()); 2690d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("(( - (1)) * i + (100)):PrimInt", GetInductionInfo(sub, 0).c_str()); 2700d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((100) * i + (0)):PrimInt", GetInductionInfo(mul, 0).c_str()); 2710d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((2) * i + (0)):PrimInt", GetInductionInfo(shl, 0).c_str()); 2720d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("(( - (1)) * i + (0)):PrimInt", GetInductionInfo(neg, 0).c_str()); 27330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 27430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 27530efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikTEST_F(InductionVarAnalysisTest, FindChainInduction) { 27630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Setup: 27730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // k = 0; 27830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i = 0; i < 100; i++) { 279e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = k + 100; 280e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[k] = 0; 281e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = k - 1; 282e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[k] = 0; 28330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 28430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildLoopNest(1); 285badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k = InsertLoopPhi(0, 0); 286badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(constant0_); 287badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 28830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction *add = InsertInstruction( 289badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0); 290badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store1 = InsertArrayStore(add, 0); 29130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction *sub = InsertInstruction( 292badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HSub(Primitive::kPrimInt, add, constant1_), 0); 293badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store2 = InsertArrayStore(sub, 0); 294badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(sub); 29530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik PerformInductionVarAnalysis(); 29630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2970d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("(((100) - (1)) * i + (100)):PrimInt", 298e609b7cf9996389e6e693f149489737436172a2cAart Bik GetInductionInfo(store1->InputAt(1), 0).c_str()); 2990d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("(((100) - (1)) * i + ((100) - (1))):PrimInt", 300e609b7cf9996389e6e693f149489737436172a2cAart Bik GetInductionInfo(store2->InputAt(1), 0).c_str()); 30130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 30230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 30330efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikTEST_F(InductionVarAnalysisTest, FindTwoWayBasicInduction) { 30430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Setup: 30530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // k = 0; 30630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i = 0; i < 100; i++) { 307e609b7cf9996389e6e693f149489737436172a2cAart Bik // if () k = k + 1; 308e609b7cf9996389e6e693f149489737436172a2cAart Bik // else k = k + 1; 309e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[k] = 0; 31030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 31130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildLoopNest(1); 312badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k_header = InsertLoopPhi(0, 0); 313badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k_header->AddInput(constant0_); 314badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 31530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* ifTrue; 31630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* ifFalse; 317badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k_body = BuildIf(0, &ifTrue, &ifFalse); 318badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 31930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // True-branch. 320badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant1_); 32130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ifTrue->AddInstruction(inc1); 322badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k_body->AddInput(inc1); 32330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // False-branch. 324badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant1_); 32530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ifFalse->AddInstruction(inc2); 326badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k_body->AddInput(inc2); 32730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Merge over a phi. 328badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store = InsertArrayStore(k_body, 0); 329badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k_header->AddInput(k_body); 33030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik PerformInductionVarAnalysis(); 33130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 3320d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str()); 3337829691e27c528ca52753dd98bcb4785e328388aAart Bik 3347829691e27c528ca52753dd98bcb4785e328388aAart Bik // Both increments get same induction. 3357829691e27c528ca52753dd98bcb4785e328388aAart Bik EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc1)); 3367829691e27c528ca52753dd98bcb4785e328388aAart Bik EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc2)); 33730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 33830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 33930efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikTEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) { 34030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Setup: 34130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i = 0; i < 100; i++) { 342e609b7cf9996389e6e693f149489737436172a2cAart Bik // if () k = i + 1; 343e609b7cf9996389e6e693f149489737436172a2cAart Bik // else k = i + 1; 344e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[k] = 0; 34530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 34630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildLoopNest(1); 34730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* ifTrue; 34830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* ifFalse; 349badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k = BuildIf(0, &ifTrue, &ifFalse); 350badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 35130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // True-branch. 352badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, basic_[0], constant1_); 35330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ifTrue->AddInstruction(inc1); 354badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(inc1); 35530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // False-branch. 356badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, basic_[0], constant1_); 35730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ifFalse->AddInstruction(inc2); 358badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(inc2); 35930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Merge over a phi. 360badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store = InsertArrayStore(k, 0); 36130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik PerformInductionVarAnalysis(); 36230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 3630d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str()); 36430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 36530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 36630efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikTEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) { 36730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Setup: 36830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // k = 0; 36930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i = 0; i < 100; i++) { 370e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[k] = 0; 371e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 100 - i; 37230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 37330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildLoopNest(1); 374badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k = InsertLoopPhi(0, 0); 375badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(constant0_); 376badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 377badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store = InsertArrayStore(k, 0); 37830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction *sub = InsertInstruction( 379badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0); 380badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(sub); 38130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik PerformInductionVarAnalysis(); 38230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 3830d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)):PrimInt):PrimInt", 384e609b7cf9996389e6e693f149489737436172a2cAart Bik GetInductionInfo(store->InputAt(1), 0).c_str()); 38530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 38630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 38730efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikTEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) { 38830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Setup: 38930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // k = 0; 39030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // t = 100; 39130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i = 0; i < 100; i++) { 392e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[k] = 0; 393e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = t; 394e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = 100 - i; 39530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 39630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildLoopNest(1); 397badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k = InsertLoopPhi(0, 0); 398badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(constant0_); 399badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* t = InsertLoopPhi(1, 0); 400badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil t->AddInput(constant100_); 401badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 402badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store = InsertArrayStore(k, 0); 403badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(t); 40430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction *sub = InsertInstruction( 405badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0], 0), 0); 406badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil t->AddInput(sub); 40730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik PerformInductionVarAnalysis(); 40830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 4090d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("wrap((0), wrap((100), (( - (1)) * i + (100)):PrimInt):PrimInt):PrimInt", 410e609b7cf9996389e6e693f149489737436172a2cAart Bik GetInductionInfo(store->InputAt(1), 0).c_str()); 411e609b7cf9996389e6e693f149489737436172a2cAart Bik} 412e609b7cf9996389e6e693f149489737436172a2cAart Bik 413e609b7cf9996389e6e693f149489737436172a2cAart BikTEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) { 414e609b7cf9996389e6e693f149489737436172a2cAart Bik // Setup: 415e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 0; 416e609b7cf9996389e6e693f149489737436172a2cAart Bik // for (int i = 0; i < 100; i++) { 417e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = k + 100; 418e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = k - 100; 419e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = k * 100; 420e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = k << 1; 421e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = - k; 422e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = i << 1; 423e609b7cf9996389e6e693f149489737436172a2cAart Bik // } 424e609b7cf9996389e6e693f149489737436172a2cAart Bik BuildLoopNest(1); 425badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k = InsertLoopPhi(0, 0); 426badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(constant0_); 427badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 428e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *add = InsertInstruction( 429badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0); 430e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *sub = InsertInstruction( 431badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HSub(Primitive::kPrimInt, k, constant100_), 0); 432e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *mul = InsertInstruction( 433badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HMul(Primitive::kPrimInt, k, constant100_), 0); 434e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *shl = InsertInstruction( 435badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HShl(Primitive::kPrimInt, k, constant1_), 0); 436e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *neg = InsertInstruction( 437badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HNeg(Primitive::kPrimInt, k), 0); 438badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput( 439badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil InsertInstruction(new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0)); 440e609b7cf9996389e6e693f149489737436172a2cAart Bik PerformInductionVarAnalysis(); 441e609b7cf9996389e6e693f149489737436172a2cAart Bik 4420d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("wrap((100), ((2) * i + (100)):PrimInt):PrimInt", 4430d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(add, 0).c_str()); 4440d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("wrap(((0) - (100)), ((2) * i + ((0) - (100))):PrimInt):PrimInt", 4450d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(sub, 0).c_str()); 4460d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("wrap((0), (((2) * (100)) * i + (0)):PrimInt):PrimInt", 4470d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(mul, 0).c_str()); 4480d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("wrap((0), (((2) * (2)) * i + (0)):PrimInt):PrimInt", 4490d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(shl, 0).c_str()); 4500d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("wrap((0), (( - (2)) * i + (0)):PrimInt):PrimInt", 4510d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(neg, 0).c_str()); 452e609b7cf9996389e6e693f149489737436172a2cAart Bik} 453e609b7cf9996389e6e693f149489737436172a2cAart Bik 454e609b7cf9996389e6e693f149489737436172a2cAart BikTEST_F(InductionVarAnalysisTest, FindPeriodicInduction) { 455e609b7cf9996389e6e693f149489737436172a2cAart Bik // Setup: 456e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 0; 457e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = 100; 458e609b7cf9996389e6e693f149489737436172a2cAart Bik // for (int i = 0; i < 100; i++) { 459e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[k] = 0; 460e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[t] = 0; 461e609b7cf9996389e6e693f149489737436172a2cAart Bik // // Swap t <-> k. 462e609b7cf9996389e6e693f149489737436172a2cAart Bik // d = t; 463e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = k; 464e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = d; 465e609b7cf9996389e6e693f149489737436172a2cAart Bik // } 466e609b7cf9996389e6e693f149489737436172a2cAart Bik BuildLoopNest(1); 467badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k = InsertLoopPhi(0, 0); 468badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(constant0_); 469badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* t = InsertLoopPhi(1, 0); 470badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil t->AddInput(constant100_); 471badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 472badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store1 = InsertArrayStore(k, 0); 473badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store2 = InsertArrayStore(t, 0); 474badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(t); 475badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil t->AddInput(k); 476e609b7cf9996389e6e693f149489737436172a2cAart Bik PerformInductionVarAnalysis(); 477e609b7cf9996389e6e693f149489737436172a2cAart Bik 4780d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("periodic((0), (100)):PrimInt", GetInductionInfo(store1->InputAt(1), 0).c_str()); 4790d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("periodic((100), (0)):PrimInt", GetInductionInfo(store2->InputAt(1), 0).c_str()); 480e609b7cf9996389e6e693f149489737436172a2cAart Bik} 481e609b7cf9996389e6e693f149489737436172a2cAart Bik 482e609b7cf9996389e6e693f149489737436172a2cAart BikTEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) { 483e609b7cf9996389e6e693f149489737436172a2cAart Bik // Setup: 484e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 0; 485e609b7cf9996389e6e693f149489737436172a2cAart Bik // for (int i = 0; i < 100; i++) { 486e609b7cf9996389e6e693f149489737436172a2cAart Bik // a[k] = 0; 487e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 1 - k; 488e609b7cf9996389e6e693f149489737436172a2cAart Bik // } 489e609b7cf9996389e6e693f149489737436172a2cAart Bik BuildLoopNest(1); 490badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k = InsertLoopPhi(0, 0); 491badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(constant0_); 492badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 493badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store = InsertArrayStore(k, 0); 494e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *sub = InsertInstruction( 495badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k), 0); 496badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k->AddInput(sub); 497e609b7cf9996389e6e693f149489737436172a2cAart Bik PerformInductionVarAnalysis(); 498e609b7cf9996389e6e693f149489737436172a2cAart Bik 4990d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("periodic((0), (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str()); 5000d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(sub, 0).c_str()); 501e609b7cf9996389e6e693f149489737436172a2cAart Bik} 502e609b7cf9996389e6e693f149489737436172a2cAart Bik 503e609b7cf9996389e6e693f149489737436172a2cAart BikTEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) { 504e609b7cf9996389e6e693f149489737436172a2cAart Bik // Setup: 505e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 0; 506e609b7cf9996389e6e693f149489737436172a2cAart Bik // for (int i = 0; i < 100; i++) { 507e609b7cf9996389e6e693f149489737436172a2cAart Bik // k = 1 - k; 508e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = k + 100; 509e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = k - 100; 510e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = k * 100; 511e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = k << 1; 512e609b7cf9996389e6e693f149489737436172a2cAart Bik // t = - k; 513e609b7cf9996389e6e693f149489737436172a2cAart Bik // } 514e609b7cf9996389e6e693f149489737436172a2cAart Bik BuildLoopNest(1); 515badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k_header = InsertLoopPhi(0, 0); 516badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k_header->AddInput(constant0_); 517badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 518badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* k_body = InsertInstruction( 519badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k_header), 0); 520badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k_header->AddInput(k_body); 521badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 522e609b7cf9996389e6e693f149489737436172a2cAart Bik // Derived expressions. 523e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *add = InsertInstruction( 524badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HAdd(Primitive::kPrimInt, k_body, constant100_), 0); 525e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *sub = InsertInstruction( 526badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HSub(Primitive::kPrimInt, k_body, constant100_), 0); 527e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *mul = InsertInstruction( 528badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HMul(Primitive::kPrimInt, k_body, constant100_), 0); 529e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *shl = InsertInstruction( 530badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HShl(Primitive::kPrimInt, k_body, constant1_), 0); 531e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction *neg = InsertInstruction( 532badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HNeg(Primitive::kPrimInt, k_body), 0); 533e609b7cf9996389e6e693f149489737436172a2cAart Bik PerformInductionVarAnalysis(); 534e609b7cf9996389e6e693f149489737436172a2cAart Bik 5350d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("periodic(((1) + (100)), (100)):PrimInt", GetInductionInfo(add, 0).c_str()); 5360d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("periodic(((1) - (100)), ((0) - (100))):PrimInt", GetInductionInfo(sub, 0).c_str()); 5370d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("periodic((100), (0)):PrimInt", GetInductionInfo(mul, 0).c_str()); 5380d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("periodic((2), (0)):PrimInt", GetInductionInfo(shl, 0).c_str()); 5390d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("periodic(( - (1)), (0)):PrimInt", GetInductionInfo(neg, 0).c_str()); 54030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 54130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 54230efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikTEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) { 54330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Setup: 54430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // k = 0; 54530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i_0 = 0; i_0 < 100; i_0++) { 54630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // .. 54730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // for (int i_9 = 0; i_9 < 100; i_9++) { 54830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // k = 1 + k; 54930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // a[k] = 0; 55030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 55130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // .. 55230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // } 55330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik BuildLoopNest(10); 554badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 555badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HPhi* k[10]; 556badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil for (int d = 0; d < 10; d++) { 557badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k[d] = InsertLoopPhi(0, d); 558badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil } 559badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 56030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction *inc = InsertInstruction( 561badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil new (&allocator_) HAdd(Primitive::kPrimInt, constant1_, k[9]), 9); 562badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HInstruction* store = InsertArrayStore(inc, 9); 563badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 564badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil for (int d = 0; d < 10; d++) { 5656dd10fa29e47d9041f5dee85a43a9615299e22c2David Brazdil k[d]->AddInput((d != 0) ? k[d - 1] : constant0_); 566badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil k[d]->AddInput((d != 9) ? k[d + 1] : inc); 567badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil } 56830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik PerformInductionVarAnalysis(); 56930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 570e609b7cf9996389e6e693f149489737436172a2cAart Bik // Avoid exact phi number, since that depends on the SSA building phase. 571e609b7cf9996389e6e693f149489737436172a2cAart Bik std::regex r("\\(\\(1\\) \\* i \\+ " 5720d345cf8db01f40db250f80de5104e0df24234faAart Bik "\\(\\(1\\) \\+ \\(\\d+:Phi\\)\\)\\):PrimInt"); 57330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 57430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik for (int d = 0; d < 10; d++) { 57530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (d == 9) { 576e609b7cf9996389e6e693f149489737436172a2cAart Bik EXPECT_TRUE(std::regex_match(GetInductionInfo(store->InputAt(1), d), r)); 57730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else { 578e609b7cf9996389e6e693f149489737436172a2cAart Bik EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str()); 57930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 5800d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(increment_[d], d).c_str()); 581d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Trip-count. 58222f058726d35dd8f40b3763649e61740b3d22535Aart Bik EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", 5839401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str()); 58430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 58530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 58630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 5877829691e27c528ca52753dd98bcb4785e328388aAart BikTEST_F(InductionVarAnalysisTest, ByteInductionIntLoopControl) { 5887829691e27c528ca52753dd98bcb4785e328388aAart Bik // Setup: 5897829691e27c528ca52753dd98bcb4785e328388aAart Bik // for (int i = 0; i < 100; i++) { 5907829691e27c528ca52753dd98bcb4785e328388aAart Bik // k = (byte) i; 5917829691e27c528ca52753dd98bcb4785e328388aAart Bik // a[k] = 0; 5927829691e27c528ca52753dd98bcb4785e328388aAart Bik // a[i] = 0; 5937829691e27c528ca52753dd98bcb4785e328388aAart Bik // } 5947829691e27c528ca52753dd98bcb4785e328388aAart Bik BuildLoopNest(1); 5957829691e27c528ca52753dd98bcb4785e328388aAart Bik HInstruction *conv = InsertInstruction( 5967829691e27c528ca52753dd98bcb4785e328388aAart Bik new (&allocator_) HTypeConversion(Primitive::kPrimByte, basic_[0], -1), 0); 5977829691e27c528ca52753dd98bcb4785e328388aAart Bik HInstruction* store1 = InsertArrayStore(conv, 0); 5987829691e27c528ca52753dd98bcb4785e328388aAart Bik HInstruction* store2 = InsertArrayStore(basic_[0], 0); 5997829691e27c528ca52753dd98bcb4785e328388aAart Bik PerformInductionVarAnalysis(); 6007829691e27c528ca52753dd98bcb4785e328388aAart Bik 6017829691e27c528ca52753dd98bcb4785e328388aAart Bik // Regular int induction (i) is "transferred" over conversion into byte induction (k). 6027829691e27c528ca52753dd98bcb4785e328388aAart Bik EXPECT_STREQ("((1) * i + (0)):PrimByte", GetInductionInfo(store1->InputAt(1), 0).c_str()); 6037829691e27c528ca52753dd98bcb4785e328388aAart Bik EXPECT_STREQ("((1) * i + (0)):PrimInt", GetInductionInfo(store2->InputAt(1), 0).c_str()); 6047829691e27c528ca52753dd98bcb4785e328388aAart Bik EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(increment_[0], 0).c_str()); 6057829691e27c528ca52753dd98bcb4785e328388aAart Bik 6067829691e27c528ca52753dd98bcb4785e328388aAart Bik // Type matters! 6077829691e27c528ca52753dd98bcb4785e328388aAart Bik EXPECT_FALSE(HaveSameInduction(store1->InputAt(1), store2->InputAt(1))); 6087829691e27c528ca52753dd98bcb4785e328388aAart Bik 6097829691e27c528ca52753dd98bcb4785e328388aAart Bik // Trip-count. 6107829691e27c528ca52753dd98bcb4785e328388aAart Bik EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", 6117829691e27c528ca52753dd98bcb4785e328388aAart Bik GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 6127829691e27c528ca52753dd98bcb4785e328388aAart Bik} 6137829691e27c528ca52753dd98bcb4785e328388aAart Bik 6140d345cf8db01f40db250f80de5104e0df24234faAart BikTEST_F(InductionVarAnalysisTest, ByteLoopControl1) { 6150d345cf8db01f40db250f80de5104e0df24234faAart Bik // Setup: 6160d345cf8db01f40db250f80de5104e0df24234faAart Bik // for (byte i = -128; i < 127; i++) { // just fits! 6170d345cf8db01f40db250f80de5104e0df24234faAart Bik // } 6180d345cf8db01f40db250f80de5104e0df24234faAart Bik BuildLoopNest(1); 6190d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0); 6200d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 6210d345cf8db01f40db250f80de5104e0df24234faAart Bik ifs->ReplaceInput(graph_->GetIntConstant(127), 1); 6220d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimByte, increment_[0], -1); 6230d345cf8db01f40db250f80de5104e0df24234faAart Bik loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 6240d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(conv, 1); 6250d345cf8db01f40db250f80de5104e0df24234faAart Bik PerformInductionVarAnalysis(); 6260d345cf8db01f40db250f80de5104e0df24234faAart Bik 6270d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + ((-128) + (1))):PrimByte", GetInductionInfo(increment_[0], 0).c_str()); 6280d345cf8db01f40db250f80de5104e0df24234faAart Bik // Trip-count. 6290d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("(((127) - (-128)) (TC-loop) ((-128) < (127)))", 6300d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 6310d345cf8db01f40db250f80de5104e0df24234faAart Bik} 6320d345cf8db01f40db250f80de5104e0df24234faAart Bik 6330d345cf8db01f40db250f80de5104e0df24234faAart BikTEST_F(InductionVarAnalysisTest, ByteLoopControl2) { 6340d345cf8db01f40db250f80de5104e0df24234faAart Bik // Setup: 6350d345cf8db01f40db250f80de5104e0df24234faAart Bik // for (byte i = -128; i < 128; i++) { // infinite loop! 6360d345cf8db01f40db250f80de5104e0df24234faAart Bik // } 6370d345cf8db01f40db250f80de5104e0df24234faAart Bik BuildLoopNest(1); 6380d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0); 6390d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 6400d345cf8db01f40db250f80de5104e0df24234faAart Bik ifs->ReplaceInput(graph_->GetIntConstant(128), 1); 6410d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimByte, increment_[0], -1); 6420d345cf8db01f40db250f80de5104e0df24234faAart Bik loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 6430d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(conv, 1); 6440d345cf8db01f40db250f80de5104e0df24234faAart Bik PerformInductionVarAnalysis(); 6450d345cf8db01f40db250f80de5104e0df24234faAart Bik 6460d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + ((-128) + (1))):PrimByte", GetInductionInfo(increment_[0], 0).c_str()); 6470d345cf8db01f40db250f80de5104e0df24234faAart Bik // Trip-count undefined. 6480d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 6490d345cf8db01f40db250f80de5104e0df24234faAart Bik} 6500d345cf8db01f40db250f80de5104e0df24234faAart Bik 6510d345cf8db01f40db250f80de5104e0df24234faAart BikTEST_F(InductionVarAnalysisTest, ShortLoopControl1) { 6520d345cf8db01f40db250f80de5104e0df24234faAart Bik // Setup: 6530d345cf8db01f40db250f80de5104e0df24234faAart Bik // for (short i = -32768; i < 32767; i++) { // just fits! 6540d345cf8db01f40db250f80de5104e0df24234faAart Bik // } 6550d345cf8db01f40db250f80de5104e0df24234faAart Bik BuildLoopNest(1); 6560d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0); 6570d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 6580d345cf8db01f40db250f80de5104e0df24234faAart Bik ifs->ReplaceInput(graph_->GetIntConstant(32767), 1); 6590d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimShort, increment_[0], -1); 6600d345cf8db01f40db250f80de5104e0df24234faAart Bik loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 6610d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(conv, 1); 6620d345cf8db01f40db250f80de5104e0df24234faAart Bik PerformInductionVarAnalysis(); 6630d345cf8db01f40db250f80de5104e0df24234faAart Bik 6640d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + ((-32768) + (1))):PrimShort", 6650d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(increment_[0], 0).c_str()); 6660d345cf8db01f40db250f80de5104e0df24234faAart Bik // Trip-count. 6670d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("(((32767) - (-32768)) (TC-loop) ((-32768) < (32767)))", 6680d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 6690d345cf8db01f40db250f80de5104e0df24234faAart Bik} 6700d345cf8db01f40db250f80de5104e0df24234faAart Bik 6710d345cf8db01f40db250f80de5104e0df24234faAart BikTEST_F(InductionVarAnalysisTest, ShortLoopControl2) { 6720d345cf8db01f40db250f80de5104e0df24234faAart Bik // Setup: 6730d345cf8db01f40db250f80de5104e0df24234faAart Bik // for (short i = -32768; i < 32768; i++) { // infinite loop! 6740d345cf8db01f40db250f80de5104e0df24234faAart Bik // } 6750d345cf8db01f40db250f80de5104e0df24234faAart Bik BuildLoopNest(1); 6760d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0); 6770d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 6780d345cf8db01f40db250f80de5104e0df24234faAart Bik ifs->ReplaceInput(graph_->GetIntConstant(32768), 1); 6790d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimShort, increment_[0], -1); 6800d345cf8db01f40db250f80de5104e0df24234faAart Bik loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 6810d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(conv, 1); 6820d345cf8db01f40db250f80de5104e0df24234faAart Bik PerformInductionVarAnalysis(); 6830d345cf8db01f40db250f80de5104e0df24234faAart Bik 6840d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + ((-32768) + (1))):PrimShort", 6850d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(increment_[0], 0).c_str()); 6860d345cf8db01f40db250f80de5104e0df24234faAart Bik // Trip-count undefined. 6870d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 6880d345cf8db01f40db250f80de5104e0df24234faAart Bik} 6890d345cf8db01f40db250f80de5104e0df24234faAart Bik 6900d345cf8db01f40db250f80de5104e0df24234faAart BikTEST_F(InductionVarAnalysisTest, CharLoopControl1) { 6910d345cf8db01f40db250f80de5104e0df24234faAart Bik // Setup: 6920d345cf8db01f40db250f80de5104e0df24234faAart Bik // for (char i = 0; i < 65535; i++) { // just fits! 6930d345cf8db01f40db250f80de5104e0df24234faAart Bik // } 6940d345cf8db01f40db250f80de5104e0df24234faAart Bik BuildLoopNest(1); 6950d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 6960d345cf8db01f40db250f80de5104e0df24234faAart Bik ifs->ReplaceInput(graph_->GetIntConstant(65535), 1); 6970d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimChar, increment_[0], -1); 6980d345cf8db01f40db250f80de5104e0df24234faAart Bik loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 6990d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(conv, 1); 7000d345cf8db01f40db250f80de5104e0df24234faAart Bik PerformInductionVarAnalysis(); 7010d345cf8db01f40db250f80de5104e0df24234faAart Bik 7020d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + (1)):PrimChar", GetInductionInfo(increment_[0], 0).c_str()); 7030d345cf8db01f40db250f80de5104e0df24234faAart Bik // Trip-count. 7040d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((65535) (TC-loop) ((0) < (65535)))", 7050d345cf8db01f40db250f80de5104e0df24234faAart Bik GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 7060d345cf8db01f40db250f80de5104e0df24234faAart Bik} 7070d345cf8db01f40db250f80de5104e0df24234faAart Bik 7080d345cf8db01f40db250f80de5104e0df24234faAart BikTEST_F(InductionVarAnalysisTest, CharLoopControl2) { 7090d345cf8db01f40db250f80de5104e0df24234faAart Bik // Setup: 7100d345cf8db01f40db250f80de5104e0df24234faAart Bik // for (char i = 0; i < 65536; i++) { // infinite loop! 7110d345cf8db01f40db250f80de5104e0df24234faAart Bik // } 7120d345cf8db01f40db250f80de5104e0df24234faAart Bik BuildLoopNest(1); 7130d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 7140d345cf8db01f40db250f80de5104e0df24234faAart Bik ifs->ReplaceInput(graph_->GetIntConstant(65536), 1); 7150d345cf8db01f40db250f80de5104e0df24234faAart Bik HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimChar, increment_[0], -1); 7160d345cf8db01f40db250f80de5104e0df24234faAart Bik loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 7170d345cf8db01f40db250f80de5104e0df24234faAart Bik basic_[0]->ReplaceInput(conv, 1); 7180d345cf8db01f40db250f80de5104e0df24234faAart Bik PerformInductionVarAnalysis(); 7190d345cf8db01f40db250f80de5104e0df24234faAart Bik 7200d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("((1) * i + (1)):PrimChar", GetInductionInfo(increment_[0], 0).c_str()); 7210d345cf8db01f40db250f80de5104e0df24234faAart Bik // Trip-count undefined. 7220d345cf8db01f40db250f80de5104e0df24234faAart Bik EXPECT_STREQ("", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 7230d345cf8db01f40db250f80de5104e0df24234faAart Bik} 7240d345cf8db01f40db250f80de5104e0df24234faAart Bik 72530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} // namespace art 726