Home | History | Annotate | Download | only in optimizing 
      1 /*
      2  * Copyright (C) 2014 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef ART_COMPILER_OPTIMIZING_LOCATIONS_H_
     18 #define ART_COMPILER_OPTIMIZING_LOCATIONS_H_
     19 
     20 #include "base/bit_field.h"
     21 #include "utils/allocation.h"
     22 #include "utils/growable_array.h"
     23 #include "utils/managed_register.h"
     24 
     25 namespace art {
     26 
     27 class HConstant;
     28 class HInstruction;
     29 
     30 /**
     31  * A Location is an abstraction over the potential location
     32  * of an instruction. It could be in register or stack.
     33  */
     34 class Location : public ValueObject {
     35  public:
     36   enum Kind {
     37     kInvalid = 0,
     38     kConstant = 1,
     39     kStackSlot = 2,  // Word size slot.
     40     kDoubleStackSlot = 3,  // 64bit stack slot.
     41     kRegister = 4,
     42     // On 32bits architectures, quick can pass a long where the
     43     // low bits are in the last parameter register, and the high
     44     // bits are in a stack slot. The kQuickParameter kind is for
     45     // handling this special case.
     46     kQuickParameter = 5,
     47 
     48     // Unallocated location represents a location that is not fixed and can be
     49     // allocated by a register allocator.  Each unallocated location has
     50     // a policy that specifies what kind of location is suitable. Payload
     51     // contains register allocation policy.
     52     kUnallocated = 6,
     53   };
     54 
     55   Location() : value_(kInvalid) {
     56     // Verify that non-tagged location kinds do not interfere with kConstantTag.
     57     COMPILE_ASSERT((kInvalid & kLocationTagMask) != kConstant, TagError);
     58     COMPILE_ASSERT((kUnallocated & kLocationTagMask) != kConstant, TagError);
     59     COMPILE_ASSERT((kStackSlot & kLocationTagMask) != kConstant, TagError);
     60     COMPILE_ASSERT((kDoubleStackSlot & kLocationTagMask) != kConstant, TagError);
     61     COMPILE_ASSERT((kRegister & kLocationTagMask) != kConstant, TagError);
     62     COMPILE_ASSERT((kConstant & kLocationTagMask) == kConstant, TagError);
     63     COMPILE_ASSERT((kQuickParameter & kLocationTagMask) == kConstant, TagError);
     64 
     65     DCHECK(!IsValid());
     66   }
     67 
     68   Location(const Location& other) : ValueObject(), value_(other.value_) {}
     69 
     70   Location& operator=(const Location& other) {
     71     value_ = other.value_;
     72     return *this;
     73   }
     74 
     75   bool IsConstant() const {
     76     return (value_ & kLocationTagMask) == kConstant;
     77   }
     78 
     79   static Location ConstantLocation(HConstant* constant) {
     80     DCHECK(constant != nullptr);
     81     return Location(kConstant | reinterpret_cast<uword>(constant));
     82   }
     83 
     84   HConstant* GetConstant() const {
     85     DCHECK(IsConstant());
     86     return reinterpret_cast<HConstant*>(value_ & ~kLocationTagMask);
     87   }
     88 
     89   bool IsValid() const {
     90     return value_ != kInvalid;
     91   }
     92 
     93   bool IsInvalid() const {
     94     return !IsValid();
     95   }
     96 
     97   // Empty location. Used if there the location should be ignored.
     98   static Location NoLocation() {
     99     return Location();
    100   }
    101 
    102   // Register locations.
    103   static Location RegisterLocation(ManagedRegister reg) {
    104     return Location(kRegister, reg.RegId());
    105   }
    106 
    107   bool IsRegister() const {
    108     return GetKind() == kRegister;
    109   }
    110 
    111   ManagedRegister reg() const {
    112     DCHECK(IsRegister());
    113     return static_cast<ManagedRegister>(GetPayload());
    114   }
    115 
    116   static uword EncodeStackIndex(intptr_t stack_index) {
    117     DCHECK(-kStackIndexBias <= stack_index);
    118     DCHECK(stack_index < kStackIndexBias);
    119     return static_cast<uword>(kStackIndexBias + stack_index);
    120   }
    121 
    122   static Location StackSlot(intptr_t stack_index) {
    123     uword payload = EncodeStackIndex(stack_index);
    124     Location loc(kStackSlot, payload);
    125     // Ensure that sign is preserved.
    126     DCHECK_EQ(loc.GetStackIndex(), stack_index);
    127     return loc;
    128   }
    129 
    130   bool IsStackSlot() const {
    131     return GetKind() == kStackSlot;
    132   }
    133 
    134   static Location DoubleStackSlot(intptr_t stack_index) {
    135     uword payload = EncodeStackIndex(stack_index);
    136     Location loc(kDoubleStackSlot, payload);
    137     // Ensure that sign is preserved.
    138     DCHECK_EQ(loc.GetStackIndex(), stack_index);
    139     return loc;
    140   }
    141 
    142   bool IsDoubleStackSlot() const {
    143     return GetKind() == kDoubleStackSlot;
    144   }
    145 
    146   intptr_t GetStackIndex() const {
    147     DCHECK(IsStackSlot() || IsDoubleStackSlot());
    148     // Decode stack index manually to preserve sign.
    149     return GetPayload() - kStackIndexBias;
    150   }
    151 
    152   intptr_t GetHighStackIndex(uintptr_t word_size) const {
    153     DCHECK(IsDoubleStackSlot());
    154     // Decode stack index manually to preserve sign.
    155     return GetPayload() - kStackIndexBias + word_size;
    156   }
    157 
    158   static Location QuickParameter(uint32_t parameter_index) {
    159     return Location(kQuickParameter, parameter_index);
    160   }
    161 
    162   uint32_t GetQuickParameterIndex() const {
    163     DCHECK(IsQuickParameter());
    164     return GetPayload();
    165   }
    166 
    167   bool IsQuickParameter() const {
    168     return GetKind() == kQuickParameter;
    169   }
    170 
    171   arm::ArmManagedRegister AsArm() const;
    172   x86::X86ManagedRegister AsX86() const;
    173   x86_64::X86_64ManagedRegister AsX86_64() const;
    174 
    175   Kind GetKind() const {
    176     return KindField::Decode(value_);
    177   }
    178 
    179   bool Equals(Location other) const {
    180     return value_ == other.value_;
    181   }
    182 
    183   const char* DebugString() const {
    184     switch (GetKind()) {
    185       case kInvalid: return "I";
    186       case kRegister: return "R";
    187       case kStackSlot: return "S";
    188       case kDoubleStackSlot: return "DS";
    189       case kQuickParameter: return "Q";
    190       case kUnallocated: return "U";
    191       case kConstant: return "C";
    192     }
    193     return "?";
    194   }
    195 
    196   // Unallocated locations.
    197   enum Policy {
    198     kAny,
    199     kRequiresRegister,
    200     kSameAsFirstInput,
    201   };
    202 
    203   bool IsUnallocated() const {
    204     return GetKind() == kUnallocated;
    205   }
    206 
    207   static Location UnallocatedLocation(Policy policy) {
    208     return Location(kUnallocated, PolicyField::Encode(policy));
    209   }
    210 
    211   // Any free register is suitable to replace this unallocated location.
    212   static Location Any() {
    213     return UnallocatedLocation(kAny);
    214   }
    215 
    216   static Location RequiresRegister() {
    217     return UnallocatedLocation(kRequiresRegister);
    218   }
    219 
    220   static Location RegisterOrConstant(HInstruction* instruction);
    221 
    222   // The location of the first input to the instruction will be
    223   // used to replace this unallocated location.
    224   static Location SameAsFirstInput() {
    225     return UnallocatedLocation(kSameAsFirstInput);
    226   }
    227 
    228   Policy GetPolicy() const {
    229     DCHECK(IsUnallocated());
    230     return PolicyField::Decode(GetPayload());
    231   }
    232 
    233   uword GetEncoding() const {
    234     return GetPayload();
    235   }
    236 
    237  private:
    238   // Number of bits required to encode Kind value.
    239   static constexpr uint32_t kBitsForKind = 4;
    240   static constexpr uint32_t kBitsForPayload = kWordSize * kBitsPerByte - kBitsForKind;
    241   static constexpr uword kLocationTagMask = 0x3;
    242 
    243   explicit Location(uword value) : value_(value) {}
    244 
    245   Location(Kind kind, uword payload)
    246       : value_(KindField::Encode(kind) | PayloadField::Encode(payload)) {}
    247 
    248   uword GetPayload() const {
    249     return PayloadField::Decode(value_);
    250   }
    251 
    252   typedef BitField<Kind, 0, kBitsForKind> KindField;
    253   typedef BitField<uword, kBitsForKind, kBitsForPayload> PayloadField;
    254 
    255   // Layout for kUnallocated locations payload.
    256   typedef BitField<Policy, 0, 3> PolicyField;
    257 
    258   // Layout for stack slots.
    259   static const intptr_t kStackIndexBias =
    260       static_cast<intptr_t>(1) << (kBitsForPayload - 1);
    261 
    262   // Location either contains kind and payload fields or a tagged handle for
    263   // a constant locations. Values of enumeration Kind are selected in such a
    264   // way that none of them can be interpreted as a kConstant tag.
    265   uword value_;
    266 };
    267 
    268 /**
    269  * The code generator computes LocationSummary for each instruction so that
    270  * the instruction itself knows what code to generate: where to find the inputs
    271  * and where to place the result.
    272  *
    273  * The intent is to have the code for generating the instruction independent of
    274  * register allocation. A register allocator just has to provide a LocationSummary.
    275  */
    276 class LocationSummary : public ArenaObject {
    277  public:
    278   explicit LocationSummary(HInstruction* instruction);
    279 
    280   void SetInAt(uint32_t at, Location location) {
    281     inputs_.Put(at, location);
    282   }
    283 
    284   Location InAt(uint32_t at) const {
    285     return inputs_.Get(at);
    286   }
    287 
    288   size_t GetInputCount() const {
    289     return inputs_.Size();
    290   }
    291 
    292   void SetOut(Location location) {
    293     output_ = Location(location);
    294   }
    295 
    296   void AddTemp(Location location) {
    297     temps_.Add(location);
    298   }
    299 
    300   Location GetTemp(uint32_t at) const {
    301     return temps_.Get(at);
    302   }
    303 
    304   void SetTempAt(uint32_t at, Location location) {
    305     temps_.Put(at, location);
    306   }
    307 
    308   size_t GetTempCount() const {
    309     return temps_.Size();
    310   }
    311 
    312   Location Out() const { return output_; }
    313 
    314  private:
    315   GrowableArray<Location> inputs_;
    316   GrowableArray<Location> temps_;
    317   Location output_;
    318 
    319   DISALLOW_COPY_AND_ASSIGN(LocationSummary);
    320 };
    321 
    322 }  // namespace art
    323 
    324 #endif  // ART_COMPILER_OPTIMIZING_LOCATIONS_H_
    325