176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray/* 276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * 476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * you may not use this file except in compliance with the License. 676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * You may obtain a copy of the License at 776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * 876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * 1076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 1176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 1276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * See the License for the specific language governing permissions and 1476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * limitations under the License. 1576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray */ 1676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 1776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray#ifndef ART_COMPILER_OPTIMIZING_LOCATIONS_H_ 1876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray#define ART_COMPILER_OPTIMIZING_LOCATIONS_H_ 1976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 202aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko#include "base/arena_containers.h" 21b666f4805c8ae707ea6fd7f6c7f375e0b000dba8Mathieu Chartier#include "base/arena_object.h" 2276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray#include "base/bit_field.h" 233946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray#include "base/bit_vector.h" 240279ebb3efd653e6bb255470c99d26949c7bcd95Ian Rogers#include "base/value_object.h" 2576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 2676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffraynamespace art { 2776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 2896f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffrayclass HConstant; 2976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffrayclass HInstruction; 30424f676379f2f872acd1478672022f19f3240fc1Nicolas Geoffrayclass Location; 31424f676379f2f872acd1478672022f19f3240fc1Nicolas Geoffray 32424f676379f2f872acd1478672022f19f3240fc1Nicolas Geoffraystd::ostream& operator<<(std::ostream& os, const Location& location); 3376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 3476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray/** 3576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * A Location is an abstraction over the potential location 3676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * of an instruction. It could be in register or stack. 3776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray */ 3876c92ac73eeda2582caee39dd427ca035caf172bVladimir Markoclass Location : public ValueObject { 3976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray public: 406c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray enum OutputOverlap { 416c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray kOutputOverlap, 426c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray kNoOutputOverlap 436c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray }; 449ae0daa60c568f98ef0020e52366856ff314615fNicolas Geoffray 4576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray enum Kind { 4676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray kInvalid = 0, 4796f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray kConstant = 1, 487fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray kStackSlot = 2, // 32bit stack slot. 4996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray kDoubleStackSlot = 3, // 64bit stack slot. 507fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray 517fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray kRegister = 4, // Core register. 527fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray 537fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray // We do not use the value 5 because it conflicts with kLocationConstantMask. 5456b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray kDoNotUse5 = 5, 557fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray 561ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray kFpuRegister = 6, // Float register. 577fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray 581ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray kRegisterPair = 7, // Long register. 591ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray 601ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray kFpuRegisterPair = 8, // Double register. 611ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray 621ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray // We do not use the value 9 because it conflicts with kLocationConstantMask. 631ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray kDoNotUse9 = 9, 6456b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray 6576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Unallocated location represents a location that is not fixed and can be 6676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // allocated by a register allocator. Each unallocated location has 6776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // a policy that specifies what kind of location is suitable. Payload 6876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // contains register allocation policy. 693e6a3bf797e49b7f449256455c7e522e888687d8Mark Mendell kUnallocated = 10, 7076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray }; 7176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 7276c92ac73eeda2582caee39dd427ca035caf172bVladimir Marko Location() : ValueObject(), value_(kInvalid) { 737fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray // Verify that non-constant location kinds do not interfere with kConstant. 74785d2f2116bb57418d81bb55b55a087afee11053Andreas Gampe static_assert((kInvalid & kLocationConstantMask) != kConstant, "TagError"); 75785d2f2116bb57418d81bb55b55a087afee11053Andreas Gampe static_assert((kUnallocated & kLocationConstantMask) != kConstant, "TagError"); 76785d2f2116bb57418d81bb55b55a087afee11053Andreas Gampe static_assert((kStackSlot & kLocationConstantMask) != kConstant, "TagError"); 77785d2f2116bb57418d81bb55b55a087afee11053Andreas Gampe static_assert((kDoubleStackSlot & kLocationConstantMask) != kConstant, "TagError"); 78785d2f2116bb57418d81bb55b55a087afee11053Andreas Gampe static_assert((kRegister & kLocationConstantMask) != kConstant, "TagError"); 79785d2f2116bb57418d81bb55b55a087afee11053Andreas Gampe static_assert((kFpuRegister & kLocationConstantMask) != kConstant, "TagError"); 80785d2f2116bb57418d81bb55b55a087afee11053Andreas Gampe static_assert((kRegisterPair & kLocationConstantMask) != kConstant, "TagError"); 81785d2f2116bb57418d81bb55b55a087afee11053Andreas Gampe static_assert((kFpuRegisterPair & kLocationConstantMask) != kConstant, "TagError"); 82785d2f2116bb57418d81bb55b55a087afee11053Andreas Gampe static_assert((kConstant & kLocationConstantMask) == kConstant, "TagError"); 8396f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 8476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray DCHECK(!IsValid()); 8576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 8676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 87fa6b93c4b69e6d7ddfa2a4ed0aff01b0608c5a3aVladimir Marko Location(const Location& other) : value_(other.value_) {} 8876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 8976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray Location& operator=(const Location& other) { 9076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray value_ = other.value_; 9176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return *this; 9276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 9376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 9496f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray bool IsConstant() const { 957fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray return (value_ & kLocationConstantMask) == kConstant; 9696f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 9796f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 9896f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray static Location ConstantLocation(HConstant* constant) { 9996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray DCHECK(constant != nullptr); 10013735955f39b3b304c37d2b2840663c131262c18Ian Rogers return Location(kConstant | reinterpret_cast<uintptr_t>(constant)); 10196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 10296f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 10396f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray HConstant* GetConstant() const { 10496f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray DCHECK(IsConstant()); 1057fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray return reinterpret_cast<HConstant*>(value_ & ~kLocationConstantMask); 10696f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 10796f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 10876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray bool IsValid() const { 10976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return value_ != kInvalid; 11076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 11176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 11276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray bool IsInvalid() const { 11376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return !IsValid(); 11476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 11576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 11676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Empty location. Used if there the location should be ignored. 11776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static Location NoLocation() { 11876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return Location(); 11976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 12076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 12176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Register locations. 12256b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray static Location RegisterLocation(int reg) { 12356b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray return Location(kRegister, reg); 12456b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray } 12556b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray 12656b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray static Location FpuRegisterLocation(int reg) { 12756b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray return Location(kFpuRegister, reg); 12876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 12976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 13056b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray static Location RegisterPairLocation(int low, int high) { 13156b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray return Location(kRegisterPair, low << 16 | high); 1327fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray } 1337fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray 1341ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray static Location FpuRegisterPairLocation(int low, int high) { 1351ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray return Location(kFpuRegisterPair, low << 16 | high); 1361ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray } 1371ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray 13876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray bool IsRegister() const { 13976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return GetKind() == kRegister; 14076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 14176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 1427fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray bool IsFpuRegister() const { 1437fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray return GetKind() == kFpuRegister; 1447fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray } 1457fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray 14656b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray bool IsRegisterPair() const { 14756b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray return GetKind() == kRegisterPair; 14856b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray } 14956b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray 1501ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray bool IsFpuRegisterPair() const { 1511ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray return GetKind() == kFpuRegisterPair; 152da02afe615191a19eae9a039786c4c4fc20dbfffNicolas Geoffray } 153da02afe615191a19eae9a039786c4c4fc20dbfffNicolas Geoffray 154da02afe615191a19eae9a039786c4c4fc20dbfffNicolas Geoffray bool IsRegisterKind() const { 155da02afe615191a19eae9a039786c4c4fc20dbfffNicolas Geoffray return IsRegister() || IsFpuRegister() || IsRegisterPair() || IsFpuRegisterPair(); 1561ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray } 1571ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray 15856b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray int reg() const { 1597fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray DCHECK(IsRegister() || IsFpuRegister()); 16056b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray return GetPayload(); 16176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 16276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 163840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int low() const { 164840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(IsPair()); 165840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return GetPayload() >> 16; 166840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 167840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 168840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int high() const { 169840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(IsPair()); 170840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return GetPayload() & 0xFFFF; 171840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 172840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 17356b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray template <typename T> 174271ab9c916980209fbc6b26e5545d76e58471569Roland Levillain T AsRegister() const { 175271ab9c916980209fbc6b26e5545d76e58471569Roland Levillain DCHECK(IsRegister()); 176271ab9c916980209fbc6b26e5545d76e58471569Roland Levillain return static_cast<T>(reg()); 177271ab9c916980209fbc6b26e5545d76e58471569Roland Levillain } 178271ab9c916980209fbc6b26e5545d76e58471569Roland Levillain 179271ab9c916980209fbc6b26e5545d76e58471569Roland Levillain template <typename T> 180271ab9c916980209fbc6b26e5545d76e58471569Roland Levillain T AsFpuRegister() const { 181271ab9c916980209fbc6b26e5545d76e58471569Roland Levillain DCHECK(IsFpuRegister()); 18256b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray return static_cast<T>(reg()); 18356b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray } 18456b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray 18556b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray template <typename T> 18656b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray T AsRegisterPairLow() const { 18756b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray DCHECK(IsRegisterPair()); 188840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return static_cast<T>(low()); 18956b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray } 19056b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray 19156b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray template <typename T> 19256b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray T AsRegisterPairHigh() const { 19356b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray DCHECK(IsRegisterPair()); 194840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return static_cast<T>(high()); 19556b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray } 19656b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray 1971ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray template <typename T> 1981ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray T AsFpuRegisterPairLow() const { 1991ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray DCHECK(IsFpuRegisterPair()); 200840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return static_cast<T>(low()); 2011ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray } 2021ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray 2031ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray template <typename T> 2041ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray T AsFpuRegisterPairHigh() const { 2051ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray DCHECK(IsFpuRegisterPair()); 206840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return static_cast<T>(high()); 207840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 208840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 209840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray bool IsPair() const { 210840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return IsRegisterPair() || IsFpuRegisterPair(); 211840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 212840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 213840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray Location ToLow() const { 214234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (IsRegisterPair()) { 215234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return Location::RegisterLocation(low()); 216234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } else if (IsFpuRegisterPair()) { 217234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return Location::FpuRegisterLocation(low()); 218234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } else { 219234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray DCHECK(IsDoubleStackSlot()); 220234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return Location::StackSlot(GetStackIndex()); 221234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 222840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 223840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 224840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray Location ToHigh() const { 225234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (IsRegisterPair()) { 226234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return Location::RegisterLocation(high()); 227234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } else if (IsFpuRegisterPair()) { 228234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return Location::FpuRegisterLocation(high()); 229234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } else { 230234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray DCHECK(IsDoubleStackSlot()); 231234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return Location::StackSlot(GetHighStackIndex(4)); 232234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 2331ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray } 2341ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray 23556b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray static uintptr_t EncodeStackIndex(intptr_t stack_index) { 23676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray DCHECK(-kStackIndexBias <= stack_index); 23776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray DCHECK(stack_index < kStackIndexBias); 23856b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray return static_cast<uintptr_t>(kStackIndexBias + stack_index); 23976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 24076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 24176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static Location StackSlot(intptr_t stack_index) { 24213735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t payload = EncodeStackIndex(stack_index); 24376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray Location loc(kStackSlot, payload); 24476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Ensure that sign is preserved. 24576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray DCHECK_EQ(loc.GetStackIndex(), stack_index); 24676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return loc; 24776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 24876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 24976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray bool IsStackSlot() const { 25076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return GetKind() == kStackSlot; 25176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 25276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 25376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static Location DoubleStackSlot(intptr_t stack_index) { 25413735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t payload = EncodeStackIndex(stack_index); 25576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray Location loc(kDoubleStackSlot, payload); 25676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Ensure that sign is preserved. 25776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray DCHECK_EQ(loc.GetStackIndex(), stack_index); 25876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return loc; 25976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 26076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 26176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray bool IsDoubleStackSlot() const { 26276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return GetKind() == kDoubleStackSlot; 26376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 26476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 26576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray intptr_t GetStackIndex() const { 26676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray DCHECK(IsStackSlot() || IsDoubleStackSlot()); 26776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Decode stack index manually to preserve sign. 26876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return GetPayload() - kStackIndexBias; 26976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 27076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 27176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray intptr_t GetHighStackIndex(uintptr_t word_size) const { 27276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray DCHECK(IsDoubleStackSlot()); 27376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Decode stack index manually to preserve sign. 27476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return GetPayload() - kStackIndexBias + word_size; 27576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 27676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 27776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray Kind GetKind() const { 2783946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray return IsConstant() ? kConstant : KindField::Decode(value_); 27976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 28076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 28176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray bool Equals(Location other) const { 28276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return value_ == other.value_; 28376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 28476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 285f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray bool Contains(Location other) const { 286f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray if (Equals(other)) { 287f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray return true; 288ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } else if (IsPair() || IsDoubleStackSlot()) { 289ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return ToLow().Equals(other) || ToHigh().Equals(other); 290f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray } 291f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray return false; 292f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray } 293f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray 294ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu bool OverlapsWith(Location other) const { 295ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Only check the overlapping case that can happen with our register allocation algorithm. 296ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu bool overlap = Contains(other) || other.Contains(*this); 297ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (kIsDebugBuild && !overlap) { 298ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Note: These are also overlapping cases. But we are not able to handle them in 299ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // ParallelMoveResolverWithSwap. Make sure that we do not meet such case with our compiler. 300ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if ((IsPair() && other.IsPair()) || (IsDoubleStackSlot() && other.IsDoubleStackSlot())) { 301ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK(!Contains(other.ToLow())); 302ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK(!Contains(other.ToHigh())); 303ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 304ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 305ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return overlap; 306ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 307ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 30876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray const char* DebugString() const { 30976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray switch (GetKind()) { 31096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray case kInvalid: return "I"; 31176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray case kRegister: return "R"; 31276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray case kStackSlot: return "S"; 31376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray case kDoubleStackSlot: return "DS"; 31476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray case kUnallocated: return "U"; 31596f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray case kConstant: return "C"; 3167fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray case kFpuRegister: return "F"; 31756b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray case kRegisterPair: return "RP"; 3181ba0f596e9e4ddd778ab431237d11baa85594ebaNicolas Geoffray case kFpuRegisterPair: return "FP"; 31956b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray case kDoNotUse5: // fall-through 32056b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray case kDoNotUse9: 3217fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray LOG(FATAL) << "Should not use this location kind"; 32276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 3237fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray UNREACHABLE(); 32476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return "?"; 32576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 32676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 32776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Unallocated locations. 32876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray enum Policy { 32976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray kAny, 33076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray kRequiresRegister, 3317fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray kRequiresFpuRegister, 33276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray kSameAsFirstInput, 33376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray }; 33476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 33576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray bool IsUnallocated() const { 33676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return GetKind() == kUnallocated; 33776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 33876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 33976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static Location UnallocatedLocation(Policy policy) { 34076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return Location(kUnallocated, PolicyField::Encode(policy)); 34176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 34276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 34376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Any free register is suitable to replace this unallocated location. 34476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static Location Any() { 34576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return UnallocatedLocation(kAny); 34676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 34776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 34876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static Location RequiresRegister() { 34976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return UnallocatedLocation(kRequiresRegister); 35076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 35176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 3527fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray static Location RequiresFpuRegister() { 3537fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray return UnallocatedLocation(kRequiresFpuRegister); 3547fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray } 3557fb49da8ec62e8a10ed9419ade9f32c6b1174687Nicolas Geoffray 35696f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray static Location RegisterOrConstant(HInstruction* instruction); 357ea5af68d6dda832bdfb5978a0c5d6f86a3f67e80Mark Mendell static Location RegisterOrInt32Constant(HInstruction* instruction); 35856b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray static Location ByteRegisterOrConstant(int reg, HInstruction* instruction); 359ea5af68d6dda832bdfb5978a0c5d6f86a3f67e80Mark Mendell static Location FpuRegisterOrConstant(HInstruction* instruction); 360ea5af68d6dda832bdfb5978a0c5d6f86a3f67e80Mark Mendell static Location FpuRegisterOrInt32Constant(HInstruction* instruction); 36196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 36276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // The location of the first input to the instruction will be 36376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // used to replace this unallocated location. 36476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static Location SameAsFirstInput() { 36576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return UnallocatedLocation(kSameAsFirstInput); 36676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 36776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 36876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray Policy GetPolicy() const { 36976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray DCHECK(IsUnallocated()); 37076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return PolicyField::Decode(GetPayload()); 37176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 37276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 37313735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t GetEncoding() const { 37476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return GetPayload(); 37576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 37676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 37776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray private: 37876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Number of bits required to encode Kind value. 37976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static constexpr uint32_t kBitsForKind = 4; 38013735955f39b3b304c37d2b2840663c131262c18Ian Rogers static constexpr uint32_t kBitsForPayload = kBitsPerIntPtrT - kBitsForKind; 38113735955f39b3b304c37d2b2840663c131262c18Ian Rogers static constexpr uintptr_t kLocationConstantMask = 0x3; 38276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 38313735955f39b3b304c37d2b2840663c131262c18Ian Rogers explicit Location(uintptr_t value) : value_(value) {} 38476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 38513735955f39b3b304c37d2b2840663c131262c18Ian Rogers Location(Kind kind, uintptr_t payload) 38676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray : value_(KindField::Encode(kind) | PayloadField::Encode(payload)) {} 38776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 38813735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t GetPayload() const { 38976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray return PayloadField::Decode(value_); 39076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 39176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 39276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray typedef BitField<Kind, 0, kBitsForKind> KindField; 39313735955f39b3b304c37d2b2840663c131262c18Ian Rogers typedef BitField<uintptr_t, kBitsForKind, kBitsForPayload> PayloadField; 39476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 39576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Layout for kUnallocated locations payload. 39676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray typedef BitField<Policy, 0, 3> PolicyField; 39776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 39876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Layout for stack slots. 39976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static const intptr_t kStackIndexBias = 40076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray static_cast<intptr_t>(1) << (kBitsForPayload - 1); 40176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 40276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // Location either contains kind and payload fields or a tagged handle for 40376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // a constant locations. Values of enumeration Kind are selected in such a 40476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray // way that none of them can be interpreted as a kConstant tag. 40513735955f39b3b304c37d2b2840663c131262c18Ian Rogers uintptr_t value_; 40676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray}; 4076a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogersstd::ostream& operator<<(std::ostream& os, const Location::Kind& rhs); 4086a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogersstd::ostream& operator<<(std::ostream& os, const Location::Policy& rhs); 40976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 4103bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffrayclass RegisterSet : public ValueObject { 4113bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray public: 4123bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray RegisterSet() : core_registers_(0), floating_point_registers_(0) {} 4133bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 4143bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray void Add(Location loc) { 41556b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray if (loc.IsRegister()) { 41656b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray core_registers_ |= (1 << loc.reg()); 41756b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray } else { 41856b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray DCHECK(loc.IsFpuRegister()); 41956b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray floating_point_registers_ |= (1 << loc.reg()); 42056b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray } 4213bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 4223bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 42319a19cffd197a28ae4c9c3e59eff6352fd392241Nicolas Geoffray void Remove(Location loc) { 42419a19cffd197a28ae4c9c3e59eff6352fd392241Nicolas Geoffray if (loc.IsRegister()) { 42519a19cffd197a28ae4c9c3e59eff6352fd392241Nicolas Geoffray core_registers_ &= ~(1 << loc.reg()); 42619a19cffd197a28ae4c9c3e59eff6352fd392241Nicolas Geoffray } else { 427424f676379f2f872acd1478672022f19f3240fc1Nicolas Geoffray DCHECK(loc.IsFpuRegister()) << loc; 42819a19cffd197a28ae4c9c3e59eff6352fd392241Nicolas Geoffray floating_point_registers_ &= ~(1 << loc.reg()); 42919a19cffd197a28ae4c9c3e59eff6352fd392241Nicolas Geoffray } 43019a19cffd197a28ae4c9c3e59eff6352fd392241Nicolas Geoffray } 43119a19cffd197a28ae4c9c3e59eff6352fd392241Nicolas Geoffray 43245b83aff85a8a8dfcae0da90d010fa2d7eb299a7Nicolas Geoffray bool ContainsCoreRegister(uint32_t id) const { 4333bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray return Contains(core_registers_, id); 4343bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 4353bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 43645b83aff85a8a8dfcae0da90d010fa2d7eb299a7Nicolas Geoffray bool ContainsFloatingPointRegister(uint32_t id) const { 4373bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray return Contains(floating_point_registers_, id); 4383bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 4393bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 4403bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray static bool Contains(uint32_t register_set, uint32_t reg) { 4413bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray return (register_set & (1 << reg)) != 0; 4423bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 4433bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 44487d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray size_t GetNumberOfRegisters() const { 44587d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray return __builtin_popcount(core_registers_) + __builtin_popcount(floating_point_registers_); 44687d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray } 44787d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 448988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray uint32_t GetCoreRegisters() const { 449988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray return core_registers_; 450988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 451988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray 452988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray uint32_t GetFloatingPointRegisters() const { 453988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray return floating_point_registers_; 454988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 455988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray 4563bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray private: 4573bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray uint32_t core_registers_; 4583bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray uint32_t floating_point_registers_; 4593bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 4603bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray DISALLOW_COPY_AND_ASSIGN(RegisterSet); 4613bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray}; 4623bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 463878d58cbaf6b17a9e3dcab790754527f3ebc69e5Andreas Gampestatic constexpr bool kIntrinsified = true; 464878d58cbaf6b17a9e3dcab790754527f3ebc69e5Andreas Gampe 46576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray/** 46676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * The code generator computes LocationSummary for each instruction so that 46776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * the instruction itself knows what code to generate: where to find the inputs 46876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * and where to place the result. 46976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * 47076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * The intent is to have the code for generating the instruction independent of 47176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray * register allocation. A register allocator just has to provide a LocationSummary. 47276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray */ 4735233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Markoclass LocationSummary : public ArenaObject<kArenaAllocLocationSummary> { 47476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray public: 4753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray enum CallKind { 4763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray kNoCall, 4773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray kCallOnSlowPath, 4783946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray kCall 4793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray }; 4803946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 48171fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe LocationSummary(HInstruction* instruction, 48271fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe CallKind call_kind = kNoCall, 48371fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe bool intrinsified = false); 48476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 4858e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray void SetInAt(uint32_t at, Location location) { 4862aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko inputs_[at] = location; 48776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 48876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 48976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray Location InAt(uint32_t at) const { 4902aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko return inputs_[at]; 49176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 49276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 49376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray size_t GetInputCount() const { 4942aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko return inputs_.size(); 49576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 49676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 4976c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray void SetOut(Location location, Location::OutputOverlap overlaps = Location::kOutputOverlap) { 498829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(output_.IsInvalid()); 4998e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray output_overlaps_ = overlaps; 500f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray output_ = location; 501f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray } 502f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray 503f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray void UpdateOut(Location location) { 504829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // There are two reasons for updating an output: 505829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // 1) Parameters, where we only know the exact stack slot after 506829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // doing full register allocation. 507829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // 2) Unallocated location. 508829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(output_.IsStackSlot() || output_.IsDoubleStackSlot() || output_.IsUnallocated()); 509f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray output_ = location; 51076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 51176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 51276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray void AddTemp(Location location) { 5132aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko temps_.push_back(location); 51476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 51576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 51676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray Location GetTemp(uint32_t at) const { 5172aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko return temps_[at]; 51876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 51976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 52076716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray void SetTempAt(uint32_t at, Location location) { 5212aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(temps_[at].IsUnallocated() || temps_[at].IsInvalid()); 5222aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko temps_[at] = location; 52376716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 52476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 52576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray size_t GetTempCount() const { 5262aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko return temps_.size(); 52776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray } 52876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 5292aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko bool HasTemps() const { return !temps_.empty(); } 53094015b939060f5041d408d48717f22443e55b6adNicolas Geoffray 53176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray Location Out() const { return output_; } 53276716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 5333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray bool CanCall() const { return call_kind_ != kNoCall; } 5343bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray bool WillCall() const { return call_kind_ == kCall; } 5353bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray bool OnlyCallsOnSlowPath() const { return call_kind_ == kCallOnSlowPath; } 5363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray bool NeedsSafepoint() const { return CanCall(); } 5373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 5383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray void SetStackBit(uint32_t index) { 5393946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray stack_mask_->SetBit(index); 5403946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 5413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 5423c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray void ClearStackBit(uint32_t index) { 5433c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray stack_mask_->ClearBit(index); 5443c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } 5453c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray 5463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray void SetRegisterBit(uint32_t reg_id) { 5473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray register_mask_ |= (1 << reg_id); 5483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 5493946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 550988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray uint32_t GetRegisterMask() const { 551988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray return register_mask_; 552988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 553988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray 5543bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray bool RegisterContainsObject(uint32_t reg_id) { 5553bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray return RegisterSet::Contains(register_mask_, reg_id); 5563bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 5573bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 5583bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray void AddLiveRegister(Location location) { 5593bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray live_registers_.Add(location); 5603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 5613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 5623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BitVector* GetStackMask() const { 5633946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray return stack_mask_; 5643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 5653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 5663bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray RegisterSet* GetLiveRegisters() { 5673bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray return &live_registers_; 5683bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 5693bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 57087d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray size_t GetNumberOfLiveRegisters() const { 57187d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray return live_registers_.GetNumberOfRegisters(); 57287d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray } 57387d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 574829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray bool OutputUsesSameAs(uint32_t input_index) const { 575829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray return (input_index == 0) 5768e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray && output_.IsUnallocated() 577829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray && (output_.GetPolicy() == Location::kSameAsFirstInput); 578829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 579829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray 580829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray bool IsFixedInput(uint32_t input_index) const { 5812aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko Location input = inputs_[input_index]; 582829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray return input.IsRegister() 583988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray || input.IsFpuRegister() 584988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray || input.IsPair() 585988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray || input.IsStackSlot() 586829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray || input.IsDoubleStackSlot(); 5877690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray } 5887690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray 589829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray bool OutputCanOverlapWithInputs() const { 5906c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray return output_overlaps_ == Location::kOutputOverlap; 5918e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray } 5928e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray 59371fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe bool Intrinsified() const { 59471fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe return intrinsified_; 59571fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe } 59671fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe 5970d5a281c671444bfa75d63caf1427a8c0e6e1177Roland Levillain void SetIntrinsified(bool intrinsified) { 5980d5a281c671444bfa75d63caf1427a8c0e6e1177Roland Levillain intrinsified_ = intrinsified; 5990d5a281c671444bfa75d63caf1427a8c0e6e1177Roland Levillain } 6000d5a281c671444bfa75d63caf1427a8c0e6e1177Roland Levillain 60176716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray private: 6022aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ArenaVector<Location> inputs_; 6032aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ArenaVector<Location> temps_; 6048e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray // Whether the output overlaps with any of the inputs. If it overlaps, then it cannot 6058e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray // share the same register as the inputs. 6066c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray Location::OutputOverlap output_overlaps_; 60776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray Location output_; 6083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray const CallKind call_kind_; 6093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 6103946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Mask of objects that live in the stack. 6113946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BitVector* stack_mask_; 6123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 6133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Mask of objects that live in register. 6143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray uint32_t register_mask_; 6153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 6163946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Registers that are in use at this position. 6173bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray RegisterSet live_registers_; 61876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 61971fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe // Whether these are locations for an intrinsified call. 6200d5a281c671444bfa75d63caf1427a8c0e6e1177Roland Levillain bool intrinsified_; 62171fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe 622f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray ART_FRIEND_TEST(RegisterAllocatorTest, ExpectedInRegisterHint); 623f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray ART_FRIEND_TEST(RegisterAllocatorTest, SameAsFirstInputHint); 62476716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(LocationSummary); 62576716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray}; 62676716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 62776716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray} // namespace art 62876716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray 62976716a69a0e51b3516227e8b7e365e4b9490618cNicolas Geoffray#endif // ART_COMPILER_OPTIMIZING_LOCATIONS_H_ 630