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 "induction_var_analysis.h" 1822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik#include "induction_var_range.h" 1930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Biknamespace art { 2130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 2230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik/** 2322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik * Since graph traversal may enter a SCC at any position, an initial representation may be rotated, 2422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik * along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming 2522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik * a chain of dependences (mutual independent items may occur in arbitrary order). For proper 2622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik * classification, the lexicographically first entry-phi is rotated to the front. 2722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik */ 2822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bikstatic void RotateEntryPhiFirst(HLoopInformation* loop, 2922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik ArenaVector<HInstruction*>* scc, 3022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik ArenaVector<HInstruction*>* new_scc) { 3122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik // Find very first entry-phi. 3222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik const HInstructionList& phis = loop->GetHeader()->GetPhis(); 3322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* phi = nullptr; 3422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik size_t phi_pos = -1; 3522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik const size_t size = scc->size(); 3622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik for (size_t i = 0; i < size; i++) { 37ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko HInstruction* other = (*scc)[i]; 38f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (other->IsLoopHeaderPhi() && (phi == nullptr || phis.FoundBefore(other, phi))) { 39f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik phi = other; 4022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik phi_pos = i; 4122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik } 4222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik } 4322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 4422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik // If found, bring that entry-phi to front. 4522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik if (phi != nullptr) { 4622af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik new_scc->clear(); 4722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik for (size_t i = 0; i < size; i++) { 48ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko new_scc->push_back((*scc)[phi_pos]); 4922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik if (++phi_pos >= size) phi_pos = 0; 5022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik } 5122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik DCHECK_EQ(size, new_scc->size()); 5222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik scc->swap(*new_scc); 5322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik } 5422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik} 5522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 560d345cf8db01f40db250f80de5104e0df24234faAart Bik/** 570d345cf8db01f40db250f80de5104e0df24234faAart Bik * Returns true if the from/to types denote a narrowing, integral conversion (precision loss). 580d345cf8db01f40db250f80de5104e0df24234faAart Bik */ 590d345cf8db01f40db250f80de5104e0df24234faAart Bikstatic bool IsNarrowingIntegralConversion(Primitive::Type from, Primitive::Type to) { 600d345cf8db01f40db250f80de5104e0df24234faAart Bik switch (from) { 610d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimLong: 620d345cf8db01f40db250f80de5104e0df24234faAart Bik return to == Primitive::kPrimByte || to == Primitive::kPrimShort 630d345cf8db01f40db250f80de5104e0df24234faAart Bik || to == Primitive::kPrimChar || to == Primitive::kPrimInt; 640d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimInt: 650d345cf8db01f40db250f80de5104e0df24234faAart Bik return to == Primitive::kPrimByte || to == Primitive::kPrimShort 660d345cf8db01f40db250f80de5104e0df24234faAart Bik || to == Primitive::kPrimChar; 670d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimChar: 680d345cf8db01f40db250f80de5104e0df24234faAart Bik case Primitive::kPrimShort: 690d345cf8db01f40db250f80de5104e0df24234faAart Bik return to == Primitive::kPrimByte; 700d345cf8db01f40db250f80de5104e0df24234faAart Bik default: 710d345cf8db01f40db250f80de5104e0df24234faAart Bik return false; 720d345cf8db01f40db250f80de5104e0df24234faAart Bik } 730d345cf8db01f40db250f80de5104e0df24234faAart Bik} 740d345cf8db01f40db250f80de5104e0df24234faAart Bik 750d345cf8db01f40db250f80de5104e0df24234faAart Bik/** 760d345cf8db01f40db250f80de5104e0df24234faAart Bik * Returns narrowest data type. 770d345cf8db01f40db250f80de5104e0df24234faAart Bik */ 780d345cf8db01f40db250f80de5104e0df24234faAart Bikstatic Primitive::Type Narrowest(Primitive::Type type1, Primitive::Type type2) { 790d345cf8db01f40db250f80de5104e0df24234faAart Bik return Primitive::ComponentSize(type1) <= Primitive::ComponentSize(type2) ? type1 : type2; 800d345cf8db01f40db250f80de5104e0df24234faAart Bik} 810d345cf8db01f40db250f80de5104e0df24234faAart Bik 8230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik// 8330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik// Class methods. 8430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik// 8530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 8630efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikHInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph) 8730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik : HOptimization(graph, kInductionPassName), 8830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik global_depth_(0), 895233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko stack_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), 905233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), 915233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko map_(std::less<HInstruction*>(), 925233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), 935233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko cycle_(std::less<HInstruction*>(), 945233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), 955233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko induction_(std::less<HLoopInformation*>(), 965233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)) { 9730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 9830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 9930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bikvoid HInductionVarAnalysis::Run() { 1007d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // Detects sequence variables (generalized induction variables) during an outer to inner 1017d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // traversal of all loops using Gerlek's algorithm. The order is important to enable 1027d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // range analysis on outer loop while visiting inner loops. 1037d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik for (HReversePostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) { 10430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* graph_block = it_graph.Current(); 10515bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // Don't analyze irreducible loops. 10615bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // TODO(ajcbik): could/should we remove this restriction? 10715bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) { 10830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik VisitLoop(graph_block->GetLoopInformation()); 10930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 11030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 11130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 11230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 11330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bikvoid HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) { 11430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's 11530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // algorithm. Due to the descendant-first nature, classification happens "on-demand". 11630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik global_depth_ = 0; 117e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(stack_.empty()); 11830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik map_.clear(); 11930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 12030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) { 12130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HBasicBlock* loop_block = it_loop.Current(); 122e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(loop_block->IsInLoop()); 12330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (loop_block->GetLoopInformation() != loop) { 12430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik continue; // Inner loops already visited. 12530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 12630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Visit phi-operations and instructions. 12730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) { 12830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* instruction = it.Current(); 129e609b7cf9996389e6e693f149489737436172a2cAart Bik if (!IsVisitedNode(instruction)) { 13030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik VisitNode(loop, instruction); 13130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 13230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 13330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) { 13430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* instruction = it.Current(); 135e609b7cf9996389e6e693f149489737436172a2cAart Bik if (!IsVisitedNode(instruction)) { 13630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik VisitNode(loop, instruction); 13730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 13830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 13930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 14030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 141e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(stack_.empty()); 14230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik map_.clear(); 143d14c59564870c910bdc823081f0ed1101f599231Aart Bik 1447829691e27c528ca52753dd98bcb4785e328388aAart Bik // Determine the loop's trip-count. 145d14c59564870c910bdc823081f0ed1101f599231Aart Bik VisitControl(loop); 14630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 14730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 14830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bikvoid HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) { 14930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik const uint32_t d1 = ++global_depth_; 150e609b7cf9996389e6e693f149489737436172a2cAart Bik map_.Put(instruction, NodeInfo(d1)); 15130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik stack_.push_back(instruction); 15230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 15330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Visit all descendants. 15430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik uint32_t low = d1; 15530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik for (size_t i = 0, count = instruction->InputCount(); i < count; ++i) { 15630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik low = std::min(low, VisitDescendant(loop, instruction->InputAt(i))); 15730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 15830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 15930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Lower or found SCC? 16030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (low < d1) { 161e609b7cf9996389e6e693f149489737436172a2cAart Bik map_.find(instruction)->second.depth = low; 16230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else { 16330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik scc_.clear(); 16430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik cycle_.clear(); 16530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 16630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Pop the stack to build the SCC for classification. 16730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik while (!stack_.empty()) { 16830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HInstruction* x = stack_.back(); 16930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik scc_.push_back(x); 17030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik stack_.pop_back(); 171e609b7cf9996389e6e693f149489737436172a2cAart Bik map_.find(x)->second.done = true; 17230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (x == instruction) { 17330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik break; 17430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 17530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 17630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 1770d345cf8db01f40db250f80de5104e0df24234faAart Bik // Type of induction. 1780d345cf8db01f40db250f80de5104e0df24234faAart Bik type_ = scc_[0]->GetType(); 1790d345cf8db01f40db250f80de5104e0df24234faAart Bik 18030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Classify the SCC. 181f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (scc_.size() == 1 && !scc_[0]->IsLoopHeaderPhi()) { 18230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ClassifyTrivial(loop, scc_[0]); 18330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else { 18430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik ClassifyNonTrivial(loop); 18530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 18630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 18730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik scc_.clear(); 18830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik cycle_.clear(); 18930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 19030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 19130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 19230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bikuint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) { 19330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // If the definition is either outside the loop (loop invariant entry value) 19430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // or assigned in inner loop (inner exit value), the traversal stops. 19530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation(); 19630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (otherLoop != loop) { 19730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return global_depth_; 19830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 19930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 20030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Inspect descendant node. 201e609b7cf9996389e6e693f149489737436172a2cAart Bik if (!IsVisitedNode(instruction)) { 20230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik VisitNode(loop, instruction); 203e609b7cf9996389e6e693f149489737436172a2cAart Bik return map_.find(instruction)->second.depth; 20430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else { 205e609b7cf9996389e6e693f149489737436172a2cAart Bik auto it = map_.find(instruction); 20630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return it->second.done ? global_depth_ : it->second.depth; 20730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 20830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 20930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 21030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bikvoid HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) { 21130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* info = nullptr; 21230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (instruction->IsPhi()) { 213f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik info = TransferPhi(loop, instruction, /* input_index */ 0); 21430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else if (instruction->IsAdd()) { 21530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)), 21630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik LookupInfo(loop, instruction->InputAt(1)), kAdd); 21730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else if (instruction->IsSub()) { 21830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)), 21930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik LookupInfo(loop, instruction->InputAt(1)), kSub); 22030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else if (instruction->IsMul()) { 22130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik info = TransferMul(LookupInfo(loop, instruction->InputAt(0)), 22230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik LookupInfo(loop, instruction->InputAt(1))); 223e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (instruction->IsShl()) { 224e609b7cf9996389e6e693f149489737436172a2cAart Bik info = TransferShl(LookupInfo(loop, instruction->InputAt(0)), 225e609b7cf9996389e6e693f149489737436172a2cAart Bik LookupInfo(loop, instruction->InputAt(1)), 226e609b7cf9996389e6e693f149489737436172a2cAart Bik instruction->InputAt(0)->GetType()); 22730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else if (instruction->IsNeg()) { 22830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik info = TransferNeg(LookupInfo(loop, instruction->InputAt(0))); 2290d345cf8db01f40db250f80de5104e0df24234faAart Bik } else if (instruction->IsTypeConversion()) { 2300d345cf8db01f40db250f80de5104e0df24234faAart Bik info = TransferCnv(LookupInfo(loop, instruction->InputAt(0)), 2310d345cf8db01f40db250f80de5104e0df24234faAart Bik instruction->AsTypeConversion()->GetInputType(), 2320d345cf8db01f40db250f80de5104e0df24234faAart Bik instruction->AsTypeConversion()->GetResultType()); 2330d345cf8db01f40db250f80de5104e0df24234faAart Bik 234e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (instruction->IsBoundsCheck()) { 235e609b7cf9996389e6e693f149489737436172a2cAart Bik info = LookupInfo(loop, instruction->InputAt(0)); // Pass-through. 23630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 23730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 23830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Successfully classified? 23930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (info != nullptr) { 24030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik AssignInfo(loop, instruction, info); 24130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 24230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 24330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 24430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bikvoid HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) { 24530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik const size_t size = scc_.size(); 246e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK_GE(size, 1u); 24722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 24822af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik // Rotate proper entry-phi to front. 24922af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik if (size > 1) { 2505233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko ArenaVector<HInstruction*> other(graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)); 25122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik RotateEntryPhiFirst(loop, &scc_, &other); 25222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik } 25322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik 254f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Analyze from entry-phi onwards. 25522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik HInstruction* phi = scc_[0]; 256f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (!phi->IsLoopHeaderPhi()) { 25730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return; 25830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 259f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik 260f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // External link should be loop invariant. 261f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* initial = LookupInfo(loop, phi->InputAt(0)); 26230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (initial == nullptr || initial->induction_class != kInvariant) { 26330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return; 26430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 26530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 266f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Singleton is wrap-around induction if all internal links have the same meaning. 26730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (size == 1) { 268f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* update = TransferPhi(loop, phi, /* input_index */ 1); 26930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (update != nullptr) { 2700d345cf8db01f40db250f80de5104e0df24234faAart Bik AssignInfo(loop, phi, CreateInduction(kWrapAround, initial, update, type_)); 27130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 27230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return; 27330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 27430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 27530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns 276e609b7cf9996389e6e693f149489737436172a2cAart Bik // temporary meaning to its nodes, seeded from the phi instruction and back. 27722af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik for (size_t i = 1; i < size; i++) { 278e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* instruction = scc_[i]; 27930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* update = nullptr; 280e609b7cf9996389e6e693f149489737436172a2cAart Bik if (instruction->IsPhi()) { 281f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik update = SolvePhiAllInputs(loop, phi, instruction); 282e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (instruction->IsAdd()) { 283e609b7cf9996389e6e693f149489737436172a2cAart Bik update = SolveAddSub( 284e609b7cf9996389e6e693f149489737436172a2cAart Bik loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true); 285e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (instruction->IsSub()) { 286e609b7cf9996389e6e693f149489737436172a2cAart Bik update = SolveAddSub( 287e609b7cf9996389e6e693f149489737436172a2cAart Bik loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true); 2880d345cf8db01f40db250f80de5104e0df24234faAart Bik } else if (instruction->IsTypeConversion()) { 2890d345cf8db01f40db250f80de5104e0df24234faAart Bik update = SolveCnv(instruction->AsTypeConversion()); 29030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 29130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (update == nullptr) { 29230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return; 29330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 294e609b7cf9996389e6e693f149489737436172a2cAart Bik cycle_.Put(instruction, update); 29530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 29630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 297f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Success if all internal links received the same temporary meaning. 298f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* induction = SolvePhi(phi, /* input_index */ 1); 299f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (induction != nullptr) { 300e609b7cf9996389e6e693f149489737436172a2cAart Bik switch (induction->induction_class) { 301e609b7cf9996389e6e693f149489737436172a2cAart Bik case kInvariant: 30222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik // Classify first phi and then the rest of the cycle "on-demand". 30322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik // Statements are scanned in order. 3040d345cf8db01f40db250f80de5104e0df24234faAart Bik AssignInfo(loop, phi, CreateInduction(kLinear, induction, initial, type_)); 30522af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik for (size_t i = 1; i < size; i++) { 306e609b7cf9996389e6e693f149489737436172a2cAart Bik ClassifyTrivial(loop, scc_[i]); 307e609b7cf9996389e6e693f149489737436172a2cAart Bik } 308e609b7cf9996389e6e693f149489737436172a2cAart Bik break; 309e609b7cf9996389e6e693f149489737436172a2cAart Bik case kPeriodic: 31022af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik // Classify all elements in the cycle with the found periodic induction while 31122af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik // rotating each first element to the end. Lastly, phi is classified. 31222af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik // Statements are scanned in reverse order. 31322af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik for (size_t i = size - 1; i >= 1; i--) { 31422af3bee34d0ab1a4bd186c71ccab00366882259Aart Bik AssignInfo(loop, scc_[i], induction); 315e609b7cf9996389e6e693f149489737436172a2cAart Bik induction = RotatePeriodicInduction(induction->op_b, induction->op_a); 316e609b7cf9996389e6e693f149489737436172a2cAart Bik } 317e609b7cf9996389e6e693f149489737436172a2cAart Bik AssignInfo(loop, phi, induction); 318e609b7cf9996389e6e693f149489737436172a2cAart Bik break; 319e609b7cf9996389e6e693f149489737436172a2cAart Bik default: 320e609b7cf9996389e6e693f149489737436172a2cAart Bik break; 32130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 32230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 32330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 32430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 325e609b7cf9996389e6e693f149489737436172a2cAart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction( 326e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* induction, 327e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* last) { 328e609b7cf9996389e6e693f149489737436172a2cAart Bik // Rotates a periodic induction of the form 329e609b7cf9996389e6e693f149489737436172a2cAart Bik // (a, b, c, d, e) 330e609b7cf9996389e6e693f149489737436172a2cAart Bik // into 331e609b7cf9996389e6e693f149489737436172a2cAart Bik // (b, c, d, e, a) 332e609b7cf9996389e6e693f149489737436172a2cAart Bik // in preparation of assigning this to the previous variable in the sequence. 333e609b7cf9996389e6e693f149489737436172a2cAart Bik if (induction->induction_class == kInvariant) { 3340d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(kPeriodic, induction, last, type_); 335e609b7cf9996389e6e693f149489737436172a2cAart Bik } 3360d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction( 3370d345cf8db01f40db250f80de5104e0df24234faAart Bik kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last), type_); 338e609b7cf9996389e6e693f149489737436172a2cAart Bik} 339e609b7cf9996389e6e693f149489737436172a2cAart Bik 340f475bee067ae0f6dd2a022c823c642265f97b065Aart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop, 341f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* phi, 342f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik size_t input_index) { 343f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Match all phi inputs from input_index onwards exactly. 344f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik const size_t count = phi->InputCount(); 345f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik DCHECK_LT(input_index, count); 346f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* a = LookupInfo(loop, phi->InputAt(input_index)); 347f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik for (size_t i = input_index + 1; i < count; i++) { 348f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* b = LookupInfo(loop, phi->InputAt(i)); 349f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (!InductionEqual(a, b)) { 350f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik return nullptr; 351f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik } 35230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 353f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik return a; 35430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 35530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 35630efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a, 35730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* b, 35830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionOp op) { 359e609b7cf9996389e6e693f149489737436172a2cAart Bik // Transfer over an addition or subtraction: any invariant, linear, wrap-around, or periodic 360e609b7cf9996389e6e693f149489737436172a2cAart Bik // can be combined with an invariant to yield a similar result. Even two linear inputs can 361e609b7cf9996389e6e693f149489737436172a2cAart Bik // be combined. All other combinations fail, however. 36230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (a != nullptr && b != nullptr) { 36330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (a->induction_class == kInvariant && b->induction_class == kInvariant) { 364471a2034171346dda4539b985b95aa6370531171Aart Bik return CreateInvariantOp(op, a, b); 36530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else if (a->induction_class == kLinear && b->induction_class == kLinear) { 3660d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(kLinear, 3670d345cf8db01f40db250f80de5104e0df24234faAart Bik TransferAddSub(a->op_a, b->op_a, op), 3680d345cf8db01f40db250f80de5104e0df24234faAart Bik TransferAddSub(a->op_b, b->op_b, op), 3690d345cf8db01f40db250f80de5104e0df24234faAart Bik type_); 370e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (a->induction_class == kInvariant) { 371e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* new_a = b->op_a; 372e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* new_b = TransferAddSub(a, b->op_b, op); 373e609b7cf9996389e6e693f149489737436172a2cAart Bik if (b->induction_class != kLinear) { 374e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(b->induction_class == kWrapAround || b->induction_class == kPeriodic); 375e609b7cf9996389e6e693f149489737436172a2cAart Bik new_a = TransferAddSub(a, new_a, op); 376e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (op == kSub) { // Negation required. 377e609b7cf9996389e6e693f149489737436172a2cAart Bik new_a = TransferNeg(new_a); 378e609b7cf9996389e6e693f149489737436172a2cAart Bik } 3790d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(b->induction_class, new_a, new_b, type_); 380e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (b->induction_class == kInvariant) { 381e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* new_a = a->op_a; 382e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* new_b = TransferAddSub(a->op_b, b, op); 383e609b7cf9996389e6e693f149489737436172a2cAart Bik if (a->induction_class != kLinear) { 384e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(a->induction_class == kWrapAround || a->induction_class == kPeriodic); 385e609b7cf9996389e6e693f149489737436172a2cAart Bik new_a = TransferAddSub(new_a, b, op); 386e609b7cf9996389e6e693f149489737436172a2cAart Bik } 3870d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(a->induction_class, new_a, new_b, type_); 38830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 38930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 39030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return nullptr; 39130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 39230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 39330efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a, 39430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik InductionInfo* b) { 395e609b7cf9996389e6e693f149489737436172a2cAart Bik // Transfer over a multiplication: any invariant, linear, wrap-around, or periodic 396e609b7cf9996389e6e693f149489737436172a2cAart Bik // can be multiplied with an invariant to yield a similar but multiplied result. 397e609b7cf9996389e6e693f149489737436172a2cAart Bik // Two non-invariant inputs cannot be multiplied, however. 39830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (a != nullptr && b != nullptr) { 39930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (a->induction_class == kInvariant && b->induction_class == kInvariant) { 400471a2034171346dda4539b985b95aa6370531171Aart Bik return CreateInvariantOp(kMul, a, b); 401e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (a->induction_class == kInvariant) { 4020d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(b->induction_class, 4030d345cf8db01f40db250f80de5104e0df24234faAart Bik TransferMul(a, b->op_a), 4040d345cf8db01f40db250f80de5104e0df24234faAart Bik TransferMul(a, b->op_b), 4050d345cf8db01f40db250f80de5104e0df24234faAart Bik type_); 406e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (b->induction_class == kInvariant) { 4070d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(a->induction_class, 4080d345cf8db01f40db250f80de5104e0df24234faAart Bik TransferMul(a->op_a, b), 4090d345cf8db01f40db250f80de5104e0df24234faAart Bik TransferMul(a->op_b, b), 4100d345cf8db01f40db250f80de5104e0df24234faAart Bik type_); 411e609b7cf9996389e6e693f149489737436172a2cAart Bik } 412e609b7cf9996389e6e693f149489737436172a2cAart Bik } 413e609b7cf9996389e6e693f149489737436172a2cAart Bik return nullptr; 414e609b7cf9996389e6e693f149489737436172a2cAart Bik} 415e609b7cf9996389e6e693f149489737436172a2cAart Bik 416e609b7cf9996389e6e693f149489737436172a2cAart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(InductionInfo* a, 417e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* b, 418d14c59564870c910bdc823081f0ed1101f599231Aart Bik Primitive::Type type) { 419e609b7cf9996389e6e693f149489737436172a2cAart Bik // Transfer over a shift left: treat shift by restricted constant as equivalent multiplication. 420471a2034171346dda4539b985b95aa6370531171Aart Bik int64_t value = -1; 42197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (a != nullptr && IsExact(b, &value)) { 422e609b7cf9996389e6e693f149489737436172a2cAart Bik // Obtain the constant needed for the multiplication. This yields an existing instruction 423e609b7cf9996389e6e693f149489737436172a2cAart Bik // if the constants is already there. Otherwise, this has a side effect on the HIR. 424e609b7cf9996389e6e693f149489737436172a2cAart Bik // The restriction on the shift factor avoids generating a negative constant 425e609b7cf9996389e6e693f149489737436172a2cAart Bik // (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that generalization 426e609b7cf9996389e6e693f149489737436172a2cAart Bik // for shift factors outside [0,32) and [0,64) ranges is done by earlier simplification. 427d14c59564870c910bdc823081f0ed1101f599231Aart Bik if ((type == Primitive::kPrimInt && 0 <= value && value < 31) || 428d14c59564870c910bdc823081f0ed1101f599231Aart Bik (type == Primitive::kPrimLong && 0 <= value && value < 63)) { 429d14c59564870c910bdc823081f0ed1101f599231Aart Bik return TransferMul(a, CreateConstant(1 << value, type)); 43030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 43130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 43230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return nullptr; 43330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 43430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 43530efb4e00c2a9aa318d44486b5eacaa7178d20efAart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) { 436e609b7cf9996389e6e693f149489737436172a2cAart Bik // Transfer over a unary negation: an invariant, linear, wrap-around, or periodic input 437e609b7cf9996389e6e693f149489737436172a2cAart Bik // yields a similar but negated induction as result. 43830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (a != nullptr) { 43930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (a->induction_class == kInvariant) { 440471a2034171346dda4539b985b95aa6370531171Aart Bik return CreateInvariantOp(kNeg, nullptr, a); 44130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 4420d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(a->induction_class, TransferNeg(a->op_a), TransferNeg(a->op_b), type_); 4430d345cf8db01f40db250f80de5104e0df24234faAart Bik } 4440d345cf8db01f40db250f80de5104e0df24234faAart Bik return nullptr; 4450d345cf8db01f40db250f80de5104e0df24234faAart Bik} 4460d345cf8db01f40db250f80de5104e0df24234faAart Bik 4470d345cf8db01f40db250f80de5104e0df24234faAart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCnv(InductionInfo* a, 4480d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type from, 4490d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type to) { 4500d345cf8db01f40db250f80de5104e0df24234faAart Bik if (a != nullptr) { 4510d345cf8db01f40db250f80de5104e0df24234faAart Bik // Allow narrowing conversion in certain cases. 4520d345cf8db01f40db250f80de5104e0df24234faAart Bik if (IsNarrowingIntegralConversion(from, to)) { 4530d345cf8db01f40db250f80de5104e0df24234faAart Bik if (a->induction_class == kLinear) { 4540d345cf8db01f40db250f80de5104e0df24234faAart Bik if (a->type == to || (a->type == from && IsNarrowingIntegralConversion(from, to))) { 4550d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(kLinear, a->op_a, a->op_b, to); 4560d345cf8db01f40db250f80de5104e0df24234faAart Bik } 4570d345cf8db01f40db250f80de5104e0df24234faAart Bik } 4580d345cf8db01f40db250f80de5104e0df24234faAart Bik // TODO: other cases useful too? 4590d345cf8db01f40db250f80de5104e0df24234faAart Bik } 46030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 46130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return nullptr; 46230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 46330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 464f475bee067ae0f6dd2a022c823c642265f97b065Aart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HInstruction* phi, 465f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik size_t input_index) { 466f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Match all phi inputs from input_index onwards exactly. 467f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik const size_t count = phi->InputCount(); 468f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik DCHECK_LT(input_index, count); 469f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik auto ita = cycle_.find(phi->InputAt(input_index)); 47030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (ita != cycle_.end()) { 471f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik for (size_t i = input_index + 1; i < count; i++) { 472f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik auto itb = cycle_.find(phi->InputAt(i)); 473f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (itb == cycle_.end() || 474f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik !HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) { 47530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return nullptr; 47630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 47730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 478f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik return ita->second; 47930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 480f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik return nullptr; 481f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik} 482e609b7cf9996389e6e693f149489737436172a2cAart Bik 483f475bee067ae0f6dd2a022c823c642265f97b065Aart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs( 484f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HLoopInformation* loop, 485f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* entry_phi, 486f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* phi) { 487f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Match all phi inputs. 488f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* match = SolvePhi(phi, /* input_index */ 0); 489f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (match != nullptr) { 490f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik return match; 491f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik } 492f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik 493f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Otherwise, try to solve for a periodic seeded from phi onward. 494f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Only tight multi-statement cycles are considered in order to 495f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // simplify rotating the periodic during the final classification. 496f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (phi->IsLoopHeaderPhi() && phi->InputCount() == 2) { 497f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* a = LookupInfo(loop, phi->InputAt(0)); 498e609b7cf9996389e6e693f149489737436172a2cAart Bik if (a != nullptr && a->induction_class == kInvariant) { 499f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (phi->InputAt(1) == entry_phi) { 500f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); 5010d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(kPeriodic, a, initial, type_); 502e609b7cf9996389e6e693f149489737436172a2cAart Bik } 503f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* b = SolvePhi(phi, /* input_index */ 1); 504f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (b != nullptr && b->induction_class == kPeriodic) { 5050d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(kPeriodic, a, b, type_); 506e609b7cf9996389e6e693f149489737436172a2cAart Bik } 507e609b7cf9996389e6e693f149489737436172a2cAart Bik } 508e609b7cf9996389e6e693f149489737436172a2cAart Bik } 50930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return nullptr; 51030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 51130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 512e609b7cf9996389e6e693f149489737436172a2cAart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop, 513f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik HInstruction* entry_phi, 514e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* instruction, 515e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* x, 516e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* y, 517e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionOp op, 518e609b7cf9996389e6e693f149489737436172a2cAart Bik bool is_first_call) { 519e609b7cf9996389e6e693f149489737436172a2cAart Bik // Solve within a cycle over an addition or subtraction: adding or subtracting an 520e609b7cf9996389e6e693f149489737436172a2cAart Bik // invariant value, seeded from phi, keeps adding to the stride of the induction. 521e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* b = LookupInfo(loop, y); 522e609b7cf9996389e6e693f149489737436172a2cAart Bik if (b != nullptr && b->induction_class == kInvariant) { 523f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (x == entry_phi) { 524471a2034171346dda4539b985b95aa6370531171Aart Bik return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b); 525e609b7cf9996389e6e693f149489737436172a2cAart Bik } 526e609b7cf9996389e6e693f149489737436172a2cAart Bik auto it = cycle_.find(x); 527e609b7cf9996389e6e693f149489737436172a2cAart Bik if (it != cycle_.end()) { 528e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* a = it->second; 529e609b7cf9996389e6e693f149489737436172a2cAart Bik if (a->induction_class == kInvariant) { 530471a2034171346dda4539b985b95aa6370531171Aart Bik return CreateInvariantOp(op, a, b); 53130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 53230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 53330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 534e609b7cf9996389e6e693f149489737436172a2cAart Bik 535e609b7cf9996389e6e693f149489737436172a2cAart Bik // Try some alternatives before failing. 53630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (op == kAdd) { 537e609b7cf9996389e6e693f149489737436172a2cAart Bik // Try the other way around for an addition if considered for first time. 538e609b7cf9996389e6e693f149489737436172a2cAart Bik if (is_first_call) { 539f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik return SolveAddSub(loop, entry_phi, instruction, y, x, op, false); 540e609b7cf9996389e6e693f149489737436172a2cAart Bik } 541e609b7cf9996389e6e693f149489737436172a2cAart Bik } else if (op == kSub) { 542f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Solve within a tight cycle that is formed by exactly two instructions, 543f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // one phi and one update, for a periodic idiom of the form k = c - k; 544f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { 545e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* a = LookupInfo(loop, x); 546e609b7cf9996389e6e693f149489737436172a2cAart Bik if (a != nullptr && a->induction_class == kInvariant) { 547f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); 5480d345cf8db01f40db250f80de5104e0df24234faAart Bik return CreateInduction(kPeriodic, CreateInvariantOp(kSub, a, initial), initial, type_); 549e609b7cf9996389e6e693f149489737436172a2cAart Bik } 55030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 55130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 552e609b7cf9996389e6e693f149489737436172a2cAart Bik 55330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return nullptr; 55430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 55530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 5560d345cf8db01f40db250f80de5104e0df24234faAart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveCnv(HTypeConversion* conversion) { 5570d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type from = conversion->GetInputType(); 5580d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type to = conversion->GetResultType(); 5590d345cf8db01f40db250f80de5104e0df24234faAart Bik // A narrowing conversion is allowed within the cycle of a linear induction, provided that the 5600d345cf8db01f40db250f80de5104e0df24234faAart Bik // narrowest encountered type is recorded with the induction to account for the precision loss. 5610d345cf8db01f40db250f80de5104e0df24234faAart Bik if (IsNarrowingIntegralConversion(from, to)) { 5620d345cf8db01f40db250f80de5104e0df24234faAart Bik auto it = cycle_.find(conversion->GetInput()); 5630d345cf8db01f40db250f80de5104e0df24234faAart Bik if (it != cycle_.end() && it->second->induction_class == kInvariant) { 5640d345cf8db01f40db250f80de5104e0df24234faAart Bik type_ = Narrowest(type_, to); 5650d345cf8db01f40db250f80de5104e0df24234faAart Bik return it->second; 5660d345cf8db01f40db250f80de5104e0df24234faAart Bik } 5670d345cf8db01f40db250f80de5104e0df24234faAart Bik } 5680d345cf8db01f40db250f80de5104e0df24234faAart Bik return nullptr; 5690d345cf8db01f40db250f80de5104e0df24234faAart Bik} 5700d345cf8db01f40db250f80de5104e0df24234faAart Bik 571d14c59564870c910bdc823081f0ed1101f599231Aart Bikvoid HInductionVarAnalysis::VisitControl(HLoopInformation* loop) { 572d14c59564870c910bdc823081f0ed1101f599231Aart Bik HInstruction* control = loop->GetHeader()->GetLastInstruction(); 573d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (control->IsIf()) { 574d14c59564870c910bdc823081f0ed1101f599231Aart Bik HIf* ifs = control->AsIf(); 575d14c59564870c910bdc823081f0ed1101f599231Aart Bik HBasicBlock* if_true = ifs->IfTrueSuccessor(); 576d14c59564870c910bdc823081f0ed1101f599231Aart Bik HBasicBlock* if_false = ifs->IfFalseSuccessor(); 577d14c59564870c910bdc823081f0ed1101f599231Aart Bik HInstruction* if_expr = ifs->InputAt(0); 578d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Determine if loop has following structure in header. 579d14c59564870c910bdc823081f0ed1101f599231Aart Bik // loop-header: .... 580d14c59564870c910bdc823081f0ed1101f599231Aart Bik // if (condition) goto X 581d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (if_expr->IsCondition()) { 582d14c59564870c910bdc823081f0ed1101f599231Aart Bik HCondition* condition = if_expr->AsCondition(); 583d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* a = LookupInfo(loop, condition->InputAt(0)); 584d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* b = LookupInfo(loop, condition->InputAt(1)); 585d14c59564870c910bdc823081f0ed1101f599231Aart Bik Primitive::Type type = condition->InputAt(0)->GetType(); 5860d345cf8db01f40db250f80de5104e0df24234faAart Bik // Determine if the loop control uses a known sequence on an if-exit (X outside) or on 5870d345cf8db01f40db250f80de5104e0df24234faAart Bik // an if-iterate (X inside), expressed as if-iterate when passed into VisitCondition(). 5880d345cf8db01f40db250f80de5104e0df24234faAart Bik if (a == nullptr || b == nullptr) { 5890d345cf8db01f40db250f80de5104e0df24234faAart Bik return; // Loop control is not a sequence. 590d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) { 591d14c59564870c910bdc823081f0ed1101f599231Aart Bik VisitCondition(loop, a, b, type, condition->GetOppositeCondition()); 592d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) { 593d14c59564870c910bdc823081f0ed1101f599231Aart Bik VisitCondition(loop, a, b, type, condition->GetCondition()); 594d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 595d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 596d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 597d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 598d14c59564870c910bdc823081f0ed1101f599231Aart Bik 599d14c59564870c910bdc823081f0ed1101f599231Aart Bikvoid HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, 600d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* a, 601d14c59564870c910bdc823081f0ed1101f599231Aart Bik InductionInfo* b, 602d14c59564870c910bdc823081f0ed1101f599231Aart Bik Primitive::Type type, 603d14c59564870c910bdc823081f0ed1101f599231Aart Bik IfCondition cmp) { 604d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (a->induction_class == kInvariant && b->induction_class == kLinear) { 605f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Swap condition if induction is at right-hand-side (e.g. U > i is same as i < U). 606d14c59564870c910bdc823081f0ed1101f599231Aart Bik switch (cmp) { 607d14c59564870c910bdc823081f0ed1101f599231Aart Bik case kCondLT: VisitCondition(loop, b, a, type, kCondGT); break; 608d14c59564870c910bdc823081f0ed1101f599231Aart Bik case kCondLE: VisitCondition(loop, b, a, type, kCondGE); break; 609d14c59564870c910bdc823081f0ed1101f599231Aart Bik case kCondGT: VisitCondition(loop, b, a, type, kCondLT); break; 610d14c59564870c910bdc823081f0ed1101f599231Aart Bik case kCondGE: VisitCondition(loop, b, a, type, kCondLE); break; 611f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik case kCondNE: VisitCondition(loop, b, a, type, kCondNE); break; 612d14c59564870c910bdc823081f0ed1101f599231Aart Bik default: break; 613d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 614d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (a->induction_class == kLinear && b->induction_class == kInvariant) { 615f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Analyze condition with induction at left-hand-side (e.g. i < U). 6169401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik InductionInfo* lower_expr = a->op_b; 6179401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik InductionInfo* upper_expr = b; 61897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik InductionInfo* stride_expr = a->op_a; 61997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik // Constant stride? 6209401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t stride_value = 0; 62197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (!IsExact(stride_expr, &stride_value)) { 622f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik return; 623f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik } 624358af839c60db9e178f0b0bb9d430711c071b82aAart Bik // Rewrite condition i != U into strict end condition i < U or i > U if this end condition 625358af839c60db9e178f0b0bb9d430711c071b82aAart Bik // is reached exactly (tested by verifying if the loop has a unit stride and the non-strict 626358af839c60db9e178f0b0bb9d430711c071b82aAart Bik // condition would be always taken). 627358af839c60db9e178f0b0bb9d430711c071b82aAart Bik if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLE)) || 628358af839c60db9e178f0b0bb9d430711c071b82aAart Bik (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGE)))) { 6299401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik cmp = stride_value > 0 ? kCondLT : kCondGT; 630d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 6310d345cf8db01f40db250f80de5104e0df24234faAart Bik // Only accept integral condition. A mismatch between the type of condition and the induction 6320d345cf8db01f40db250f80de5104e0df24234faAart Bik // is only allowed if the, necessarily narrower, induction range fits the narrower control. 6330d345cf8db01f40db250f80de5104e0df24234faAart Bik if (type != Primitive::kPrimInt && type != Primitive::kPrimLong) { 6340d345cf8db01f40db250f80de5104e0df24234faAart Bik return; // not integral 6350d345cf8db01f40db250f80de5104e0df24234faAart Bik } else if (type != a->type && 6360d345cf8db01f40db250f80de5104e0df24234faAart Bik !FitsNarrowerControl(lower_expr, upper_expr, stride_value, a->type, cmp)) { 6370d345cf8db01f40db250f80de5104e0df24234faAart Bik return; // mismatched type 6380d345cf8db01f40db250f80de5104e0df24234faAart Bik } 639f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // Normalize a linear loop control with a nonzero stride: 640f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // stride > 0, either i < U or i <= U 641f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik // stride < 0, either i > U or i >= U 642f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) || 643f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) { 64497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik VisitTripCount(loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp); 645f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik } 646d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 647d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 648d14c59564870c910bdc823081f0ed1101f599231Aart Bik 649d14c59564870c910bdc823081f0ed1101f599231Aart Bikvoid HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, 6509401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik InductionInfo* lower_expr, 6519401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik InductionInfo* upper_expr, 65297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik InductionInfo* stride_expr, 6539401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t stride_value, 654d14c59564870c910bdc823081f0ed1101f599231Aart Bik Primitive::Type type, 655f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik IfCondition cmp) { 656d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Any loop of the general form: 657d14c59564870c910bdc823081f0ed1101f599231Aart Bik // 658d14c59564870c910bdc823081f0ed1101f599231Aart Bik // for (i = L; i <= U; i += S) // S > 0 659d14c59564870c910bdc823081f0ed1101f599231Aart Bik // or for (i = L; i >= U; i += S) // S < 0 660d14c59564870c910bdc823081f0ed1101f599231Aart Bik // .. i .. 661d14c59564870c910bdc823081f0ed1101f599231Aart Bik // 662d14c59564870c910bdc823081f0ed1101f599231Aart Bik // can be normalized into: 663d14c59564870c910bdc823081f0ed1101f599231Aart Bik // 664d14c59564870c910bdc823081f0ed1101f599231Aart Bik // for (n = 0; n < TC; n++) // where TC = (U + S - L) / S 665d14c59564870c910bdc823081f0ed1101f599231Aart Bik // .. L + S * n .. 666d14c59564870c910bdc823081f0ed1101f599231Aart Bik // 6679401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // taking the following into consideration: 668d14c59564870c910bdc823081f0ed1101f599231Aart Bik // 6699401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // (1) Using the same precision, the TC (trip-count) expression should be interpreted as 6709401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // an unsigned entity, for example, as in the following loop that uses the full range: 6719401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // for (int i = INT_MIN; i < INT_MAX; i++) // TC = UINT_MAX 6729401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // (2) The TC is only valid if the loop is taken, otherwise TC = 0, as in: 67322f058726d35dd8f40b3763649e61740b3d22535Aart Bik // for (int i = 12; i < U; i++) // TC = 0 when U < 12 6749401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // If this cannot be determined at compile-time, the TC is only valid within the 67522f058726d35dd8f40b3763649e61740b3d22535Aart Bik // loop-body proper, not the loop-header unless enforced with an explicit taken-test. 6769401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // (3) The TC is only valid if the loop is finite, otherwise TC has no value, as in: 6779401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // for (int i = 0; i <= U; i++) // TC = Inf when U = INT_MAX 6789401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // If this cannot be determined at compile-time, the TC is only valid when enforced 67922f058726d35dd8f40b3763649e61740b3d22535Aart Bik // with an explicit finite-test. 6809401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // (4) For loops which early-exits, the TC forms an upper bound, as in: 6819401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // for (int i = 0; i < 10 && ....; i++) // TC <= 10 68222f058726d35dd8f40b3763649e61740b3d22535Aart Bik InductionInfo* trip_count = upper_expr; 6839401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik const bool is_taken = IsTaken(lower_expr, upper_expr, cmp); 6849401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik const bool is_finite = IsFinite(upper_expr, stride_value, type, cmp); 6859401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik const bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1; 686d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (!cancels) { 687d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Convert exclusive integral inequality into inclusive integral inequality, 688d14c59564870c910bdc823081f0ed1101f599231Aart Bik // viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1. 689f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik if (cmp == kCondLT) { 69022f058726d35dd8f40b3763649e61740b3d22535Aart Bik trip_count = CreateInvariantOp(kSub, trip_count, CreateConstant(1, type)); 691f475bee067ae0f6dd2a022c823c642265f97b065Aart Bik } else if (cmp == kCondGT) { 69222f058726d35dd8f40b3763649e61740b3d22535Aart Bik trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type)); 693d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 694d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Compensate for stride. 69597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik trip_count = CreateInvariantOp(kAdd, trip_count, stride_expr); 696d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 69797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik trip_count = CreateInvariantOp( 69897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride_expr); 699d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Assign the trip-count expression to the loop control. Clients that use the information 7009401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // should be aware that the expression is only valid under the conditions listed above. 70122f058726d35dd8f40b3763649e61740b3d22535Aart Bik InductionOp tcKind = kTripCountInBodyUnsafe; // needs both tests 7029401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik if (is_taken && is_finite) { 70322f058726d35dd8f40b3763649e61740b3d22535Aart Bik tcKind = kTripCountInLoop; // needs neither test 7049401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik } else if (is_finite) { 70522f058726d35dd8f40b3763649e61740b3d22535Aart Bik tcKind = kTripCountInBody; // needs taken-test 7069401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik } else if (is_taken) { 70722f058726d35dd8f40b3763649e61740b3d22535Aart Bik tcKind = kTripCountInLoopUnsafe; // needs finite-test 7089401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik } 70922f058726d35dd8f40b3763649e61740b3d22535Aart Bik InductionOp op = kNop; 71022f058726d35dd8f40b3763649e61740b3d22535Aart Bik switch (cmp) { 71122f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kCondLT: op = kLT; break; 71222f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kCondLE: op = kLE; break; 71322f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kCondGT: op = kGT; break; 71422f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kCondGE: op = kGE; break; 71522f058726d35dd8f40b3763649e61740b3d22535Aart Bik default: LOG(FATAL) << "CONDITION UNREACHABLE"; 71622f058726d35dd8f40b3763649e61740b3d22535Aart Bik } 71722f058726d35dd8f40b3763649e61740b3d22535Aart Bik InductionInfo* taken_test = CreateInvariantOp(op, lower_expr, upper_expr); 71822f058726d35dd8f40b3763649e61740b3d22535Aart Bik AssignInfo(loop, 71922f058726d35dd8f40b3763649e61740b3d22535Aart Bik loop->GetHeader()->GetLastInstruction(), 7200d345cf8db01f40db250f80de5104e0df24234faAart Bik CreateTripCount(tcKind, trip_count, taken_test, type)); 7219401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik} 7229401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik 7239401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bikbool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr, 7249401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik InductionInfo* upper_expr, 7259401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik IfCondition cmp) { 7269401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t lower_value; 7279401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t upper_value; 72897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik switch (cmp) { 72997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik case kCondLT: 73097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return IsAtMost(lower_expr, &lower_value) 73197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik && IsAtLeast(upper_expr, &upper_value) 73297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik && lower_value < upper_value; 73397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik case kCondLE: 73497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return IsAtMost(lower_expr, &lower_value) 73597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik && IsAtLeast(upper_expr, &upper_value) 73697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik && lower_value <= upper_value; 73797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik case kCondGT: 73897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return IsAtLeast(lower_expr, &lower_value) 73997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik && IsAtMost(upper_expr, &upper_value) 74097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik && lower_value > upper_value; 74197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik case kCondGE: 74297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return IsAtLeast(lower_expr, &lower_value) 74397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik && IsAtMost(upper_expr, &upper_value) 74497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik && lower_value >= upper_value; 74597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik default: 74697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik LOG(FATAL) << "CONDITION UNREACHABLE"; 7479401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik } 7489401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return false; // not certain, may be untaken 7499401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik} 7509401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik 7519401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bikbool HInductionVarAnalysis::IsFinite(InductionInfo* upper_expr, 7529401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t stride_value, 7539401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik Primitive::Type type, 7549401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik IfCondition cmp) { 7550d345cf8db01f40db250f80de5104e0df24234faAart Bik const int64_t min = Primitive::MinValueOfIntegralType(type); 7560d345cf8db01f40db250f80de5104e0df24234faAart Bik const int64_t max = Primitive::MaxValueOfIntegralType(type); 7579401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik // Some rules under which it is certain at compile-time that the loop is finite. 7589401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik int64_t value; 7599401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik switch (cmp) { 7609401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik case kCondLT: 7619401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return stride_value == 1 || 76297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik (IsAtMost(upper_expr, &value) && value <= (max - stride_value + 1)); 7639401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik case kCondLE: 76497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return (IsAtMost(upper_expr, &value) && value <= (max - stride_value)); 7659401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik case kCondGT: 7669401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return stride_value == -1 || 76797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik (IsAtLeast(upper_expr, &value) && value >= (min - stride_value - 1)); 7689401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik case kCondGE: 76997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return (IsAtLeast(upper_expr, &value) && value >= (min - stride_value)); 770e9f37600e98ba21308ad4f70d9d68cf6c057bdbeAart Bik default: 771e9f37600e98ba21308ad4f70d9d68cf6c057bdbeAart Bik LOG(FATAL) << "CONDITION UNREACHABLE"; 7729401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik } 7739401f5397128ddc8dc36de923dd5e6bd4e4b5be4Aart Bik return false; // not certain, may be infinite 774d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 775d14c59564870c910bdc823081f0ed1101f599231Aart Bik 7760d345cf8db01f40db250f80de5104e0df24234faAart Bikbool HInductionVarAnalysis::FitsNarrowerControl(InductionInfo* lower_expr, 7770d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionInfo* upper_expr, 7780d345cf8db01f40db250f80de5104e0df24234faAart Bik int64_t stride_value, 7790d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::Type type, 7800d345cf8db01f40db250f80de5104e0df24234faAart Bik IfCondition cmp) { 7810d345cf8db01f40db250f80de5104e0df24234faAart Bik int64_t min = Primitive::MinValueOfIntegralType(type); 7820d345cf8db01f40db250f80de5104e0df24234faAart Bik int64_t max = Primitive::MaxValueOfIntegralType(type); 7830d345cf8db01f40db250f80de5104e0df24234faAart Bik // Inclusive test need one extra. 7840d345cf8db01f40db250f80de5104e0df24234faAart Bik if (stride_value != 1 && stride_value != -1) { 7850d345cf8db01f40db250f80de5104e0df24234faAart Bik return false; // non-unit stride 7860d345cf8db01f40db250f80de5104e0df24234faAart Bik } else if (cmp == kCondLE) { 7870d345cf8db01f40db250f80de5104e0df24234faAart Bik max--; 7880d345cf8db01f40db250f80de5104e0df24234faAart Bik } else if (cmp == kCondGE) { 7890d345cf8db01f40db250f80de5104e0df24234faAart Bik min++; 7900d345cf8db01f40db250f80de5104e0df24234faAart Bik } 7910d345cf8db01f40db250f80de5104e0df24234faAart Bik // Do both bounds fit the range? 7920e2f2ff383ecc08aabb83c62670324ee2ca28bc1Vladimir Marko // Note: The `value` is initialized to please valgrind - the compiler can reorder 7930e2f2ff383ecc08aabb83c62670324ee2ca28bc1Vladimir Marko // the return value check with the `value` check, b/27651442 . 7940e2f2ff383ecc08aabb83c62670324ee2ca28bc1Vladimir Marko int64_t value = 0; 7950d345cf8db01f40db250f80de5104e0df24234faAart Bik return IsAtLeast(lower_expr, &value) && value >= min && 7960d345cf8db01f40db250f80de5104e0df24234faAart Bik IsAtMost(lower_expr, &value) && value <= max && 7970d345cf8db01f40db250f80de5104e0df24234faAart Bik IsAtLeast(upper_expr, &value) && value >= min && 7980d345cf8db01f40db250f80de5104e0df24234faAart Bik IsAtMost(upper_expr, &value) && value <= max; 7990d345cf8db01f40db250f80de5104e0df24234faAart Bik} 8000d345cf8db01f40db250f80de5104e0df24234faAart Bik 801e609b7cf9996389e6e693f149489737436172a2cAart Bikvoid HInductionVarAnalysis::AssignInfo(HLoopInformation* loop, 802e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* instruction, 803e609b7cf9996389e6e693f149489737436172a2cAart Bik InductionInfo* info) { 804e609b7cf9996389e6e693f149489737436172a2cAart Bik auto it = induction_.find(loop); 80530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (it == induction_.end()) { 806e609b7cf9996389e6e693f149489737436172a2cAart Bik it = induction_.Put(loop, 807e609b7cf9996389e6e693f149489737436172a2cAart Bik ArenaSafeMap<HInstruction*, InductionInfo*>( 8085233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko std::less<HInstruction*>(), 8095233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis))); 81030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 811e609b7cf9996389e6e693f149489737436172a2cAart Bik it->second.Put(instruction, info); 81230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 81330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 814e609b7cf9996389e6e693f149489737436172a2cAart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop, 815e609b7cf9996389e6e693f149489737436172a2cAart Bik HInstruction* instruction) { 816e609b7cf9996389e6e693f149489737436172a2cAart Bik auto it = induction_.find(loop); 81730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (it != induction_.end()) { 818e609b7cf9996389e6e693f149489737436172a2cAart Bik auto loop_it = it->second.find(instruction); 81930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (loop_it != it->second.end()) { 82030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return loop_it->second; 82130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 82230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 8234b467ed97bc5886fb800209c0ee94df10163b88dMingyao Yang if (loop->IsDefinedOutOfTheLoop(instruction)) { 824471a2034171346dda4539b985b95aa6370531171Aart Bik InductionInfo* info = CreateInvariantFetch(instruction); 825e609b7cf9996389e6e693f149489737436172a2cAart Bik AssignInfo(loop, instruction, info); 826e609b7cf9996389e6e693f149489737436172a2cAart Bik return info; 82730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 828e609b7cf9996389e6e693f149489737436172a2cAart Bik return nullptr; 82930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 83030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 831d14c59564870c910bdc823081f0ed1101f599231Aart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateConstant(int64_t value, 832d14c59564870c910bdc823081f0ed1101f599231Aart Bik Primitive::Type type) { 833d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (type == Primitive::kPrimInt) { 834d14c59564870c910bdc823081f0ed1101f599231Aart Bik return CreateInvariantFetch(graph_->GetIntConstant(value)); 835d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 836d14c59564870c910bdc823081f0ed1101f599231Aart Bik DCHECK_EQ(type, Primitive::kPrimLong); 837d14c59564870c910bdc823081f0ed1101f599231Aart Bik return CreateInvariantFetch(graph_->GetLongConstant(value)); 838d14c59564870c910bdc823081f0ed1101f599231Aart Bik} 839d14c59564870c910bdc823081f0ed1101f599231Aart Bik 840471a2034171346dda4539b985b95aa6370531171Aart BikHInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant( 841471a2034171346dda4539b985b95aa6370531171Aart Bik InductionOp op, 842471a2034171346dda4539b985b95aa6370531171Aart Bik InductionInfo* a, 843471a2034171346dda4539b985b95aa6370531171Aart Bik InductionInfo* b) { 844471a2034171346dda4539b985b95aa6370531171Aart Bik // Perform some light-weight simplifications during construction of a new invariant. 845471a2034171346dda4539b985b95aa6370531171Aart Bik // This often safes memory and yields a more concise representation of the induction. 846471a2034171346dda4539b985b95aa6370531171Aart Bik // More exhaustive simplifications are done by later phases once induction nodes are 847471a2034171346dda4539b985b95aa6370531171Aart Bik // translated back into HIR code (e.g. by loop optimizations or BCE). 848471a2034171346dda4539b985b95aa6370531171Aart Bik int64_t value = -1; 84997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsExact(a, &value)) { 850471a2034171346dda4539b985b95aa6370531171Aart Bik if (value == 0) { 851471a2034171346dda4539b985b95aa6370531171Aart Bik // Simplify 0 + b = b, 0 * b = 0. 852471a2034171346dda4539b985b95aa6370531171Aart Bik if (op == kAdd) { 853471a2034171346dda4539b985b95aa6370531171Aart Bik return b; 854471a2034171346dda4539b985b95aa6370531171Aart Bik } else if (op == kMul) { 855471a2034171346dda4539b985b95aa6370531171Aart Bik return a; 856471a2034171346dda4539b985b95aa6370531171Aart Bik } 857d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (op == kMul) { 858d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Simplify 1 * b = b, -1 * b = -b 859d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (value == 1) { 860d14c59564870c910bdc823081f0ed1101f599231Aart Bik return b; 861d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (value == -1) { 8627d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return CreateSimplifiedInvariant(kNeg, nullptr, b); 863d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 864471a2034171346dda4539b985b95aa6370531171Aart Bik } 865471a2034171346dda4539b985b95aa6370531171Aart Bik } 86697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik if (IsExact(b, &value)) { 867471a2034171346dda4539b985b95aa6370531171Aart Bik if (value == 0) { 868d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, -0 = 0. 869471a2034171346dda4539b985b95aa6370531171Aart Bik if (op == kAdd || op == kSub) { 870471a2034171346dda4539b985b95aa6370531171Aart Bik return a; 871471a2034171346dda4539b985b95aa6370531171Aart Bik } else if (op == kMul || op == kNeg) { 872471a2034171346dda4539b985b95aa6370531171Aart Bik return b; 873471a2034171346dda4539b985b95aa6370531171Aart Bik } 874d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (op == kMul || op == kDiv) { 875d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Simplify a * 1 = a, a / 1 = a, a * -1 = -a, a / -1 = -a 876d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (value == 1) { 877d14c59564870c910bdc823081f0ed1101f599231Aart Bik return a; 878d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (value == -1) { 8797d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return CreateSimplifiedInvariant(kNeg, nullptr, a); 880d14c59564870c910bdc823081f0ed1101f599231Aart Bik } 881471a2034171346dda4539b985b95aa6370531171Aart Bik } 882471a2034171346dda4539b985b95aa6370531171Aart Bik } else if (b->operation == kNeg) { 883d14c59564870c910bdc823081f0ed1101f599231Aart Bik // Simplify a + (-b) = a - b, a - (-b) = a + b, -(-b) = b. 884d14c59564870c910bdc823081f0ed1101f599231Aart Bik if (op == kAdd) { 8857d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return CreateSimplifiedInvariant(kSub, a, b->op_b); 886d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (op == kSub) { 8877d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return CreateSimplifiedInvariant(kAdd, a, b->op_b); 888d14c59564870c910bdc823081f0ed1101f599231Aart Bik } else if (op == kNeg) { 889d14c59564870c910bdc823081f0ed1101f599231Aart Bik return b->op_b; 890471a2034171346dda4539b985b95aa6370531171Aart Bik } 8917d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } else if (b->operation == kSub) { 8927d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // Simplify - (a - b) = b - a. 8937d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik if (op == kNeg) { 8947d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return CreateSimplifiedInvariant(kSub, b->op_b, b->op_a); 8957d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } 896471a2034171346dda4539b985b95aa6370531171Aart Bik } 8970d345cf8db01f40db250f80de5104e0df24234faAart Bik return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, b->type); 898471a2034171346dda4539b985b95aa6370531171Aart Bik} 899471a2034171346dda4539b985b95aa6370531171Aart Bik 90097412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bikbool HInductionVarAnalysis::IsExact(InductionInfo* info, int64_t* value) { 90197412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return InductionVarRange(this).IsConstant(info, InductionVarRange::kExact, value); 90297412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik} 90397412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik 90497412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bikbool HInductionVarAnalysis::IsAtMost(InductionInfo* info, int64_t* value) { 90597412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtMost, value); 90697412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik} 90797412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik 90897412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bikbool HInductionVarAnalysis::IsAtLeast(InductionInfo* info, int64_t* value) { 90997412c92afb3f6630c4f0eafe6d6161862bfb4c1Aart Bik return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtLeast, value); 910471a2034171346dda4539b985b95aa6370531171Aart Bik} 911471a2034171346dda4539b985b95aa6370531171Aart Bik 9127d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bikbool HInductionVarAnalysis::InductionEqual(InductionInfo* info1, 9137d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik InductionInfo* info2) { 9147d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // Test structural equality only, without accounting for simplifications. 9157d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik if (info1 != nullptr && info2 != nullptr) { 9167d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return 9177d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik info1->induction_class == info2->induction_class && 9187d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik info1->operation == info2->operation && 9197d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik info1->fetch == info2->fetch && 9207829691e27c528ca52753dd98bcb4785e328388aAart Bik info1->type == info2->type && 9217d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik InductionEqual(info1->op_a, info2->op_a) && 9227d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik InductionEqual(info1->op_b, info2->op_b); 9237d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } 9247d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik // Otherwise only two nullptrs are considered equal. 9257d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik return info1 == info2; 9267d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik} 9277d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik 92830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bikstd::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { 92930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (info != nullptr) { 93030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (info->induction_class == kInvariant) { 93130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik std::string inv = "("; 93230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik inv += InductionToString(info->op_a); 93330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik switch (info->operation) { 93422f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kNop: inv += " @ "; break; 93522f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kAdd: inv += " + "; break; 93630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik case kSub: 93722f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kNeg: inv += " - "; break; 93822f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kMul: inv += " * "; break; 93922f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kDiv: inv += " / "; break; 94022f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kLT: inv += " < "; break; 94122f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kLE: inv += " <= "; break; 94222f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kGT: inv += " > "; break; 94322f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kGE: inv += " >= "; break; 94430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik case kFetch: 945e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(info->fetch); 9467d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik if (info->fetch->IsIntConstant()) { 9477d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik inv += std::to_string(info->fetch->AsIntConstant()->GetValue()); 9487d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik } else if (info->fetch->IsLongConstant()) { 9497d57d7f2f0328241ff07c43a93edadbc1a6697c6Aart Bik inv += std::to_string(info->fetch->AsLongConstant()->GetValue()); 950471a2034171346dda4539b985b95aa6370531171Aart Bik } else { 951471a2034171346dda4539b985b95aa6370531171Aart Bik inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName(); 952471a2034171346dda4539b985b95aa6370531171Aart Bik } 95330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik break; 95422f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kTripCountInLoop: inv += " (TC-loop) "; break; 95522f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kTripCountInBody: inv += " (TC-body) "; break; 95622f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kTripCountInLoopUnsafe: inv += " (TC-loop-unsafe) "; break; 95722f058726d35dd8f40b3763649e61740b3d22535Aart Bik case kTripCountInBodyUnsafe: inv += " (TC-body-unsafe) "; break; 95830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 95930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik inv += InductionToString(info->op_b); 9600d345cf8db01f40db250f80de5104e0df24234faAart Bik inv += ")"; 9610d345cf8db01f40db250f80de5104e0df24234faAart Bik return inv; 96230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else { 963e609b7cf9996389e6e693f149489737436172a2cAart Bik DCHECK(info->operation == kNop); 96430efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik if (info->induction_class == kLinear) { 96530efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return "(" + InductionToString(info->op_a) + " * i + " + 9660d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionToString(info->op_b) + "):" + 9670d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::PrettyDescriptor(info->type); 96830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else if (info->induction_class == kWrapAround) { 96930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return "wrap(" + InductionToString(info->op_a) + ", " + 9700d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionToString(info->op_b) + "):" + 9710d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::PrettyDescriptor(info->type); 97230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } else if (info->induction_class == kPeriodic) { 97330efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return "periodic(" + InductionToString(info->op_a) + ", " + 9740d345cf8db01f40db250f80de5104e0df24234faAart Bik InductionToString(info->op_b) + "):" + 9750d345cf8db01f40db250f80de5104e0df24234faAart Bik Primitive::PrettyDescriptor(info->type); 97630efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 97730efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 97830efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik } 97930efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik return ""; 98030efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} 98130efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik 98230efb4e00c2a9aa318d44486b5eacaa7178d20efAart Bik} // namespace art 983