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/arena_object.h"
     21 #include "base/bit_field.h"
     22 #include "base/bit_vector.h"
     23 #include "base/value_object.h"
     24 #include "utils/growable_array.h"
     25 
     26 namespace art {
     27 
     28 class HConstant;
     29 class HInstruction;
     30 class Location;
     31 
     32 std::ostream& operator<<(std::ostream& os, const Location& location);
     33 
     34 /**
     35  * A Location is an abstraction over the potential location
     36  * of an instruction. It could be in register or stack.
     37  */
     38 class Location : public ValueObject {
     39  public:
     40   enum OutputOverlap {
     41     kOutputOverlap,
     42     kNoOutputOverlap
     43   };
     44 
     45   enum Kind {
     46     kInvalid = 0,
     47     kConstant = 1,
     48     kStackSlot = 2,  // 32bit stack slot.
     49     kDoubleStackSlot = 3,  // 64bit stack slot.
     50 
     51     kRegister = 4,  // Core register.
     52 
     53     // We do not use the value 5 because it conflicts with kLocationConstantMask.
     54     kDoNotUse5 = 5,
     55 
     56     kFpuRegister = 6,  // Float register.
     57 
     58     kRegisterPair = 7,  // Long register.
     59 
     60     kFpuRegisterPair = 8,  // Double register.
     61 
     62     // We do not use the value 9 because it conflicts with kLocationConstantMask.
     63     kDoNotUse9 = 9,
     64 
     65     // Unallocated location represents a location that is not fixed and can be
     66     // allocated by a register allocator.  Each unallocated location has
     67     // a policy that specifies what kind of location is suitable. Payload
     68     // contains register allocation policy.
     69     kUnallocated = 10,
     70   };
     71 
     72   Location() : value_(kInvalid) {
     73     // Verify that non-constant location kinds do not interfere with kConstant.
     74     static_assert((kInvalid & kLocationConstantMask) != kConstant, "TagError");
     75     static_assert((kUnallocated & kLocationConstantMask) != kConstant, "TagError");
     76     static_assert((kStackSlot & kLocationConstantMask) != kConstant, "TagError");
     77     static_assert((kDoubleStackSlot & kLocationConstantMask) != kConstant, "TagError");
     78     static_assert((kRegister & kLocationConstantMask) != kConstant, "TagError");
     79     static_assert((kFpuRegister & kLocationConstantMask) != kConstant, "TagError");
     80     static_assert((kRegisterPair & kLocationConstantMask) != kConstant, "TagError");
     81     static_assert((kFpuRegisterPair & kLocationConstantMask) != kConstant, "TagError");
     82     static_assert((kConstant & kLocationConstantMask) == kConstant, "TagError");
     83 
     84     DCHECK(!IsValid());
     85   }
     86 
     87   Location(const Location& other) : ValueObject(), value_(other.value_) {}
     88 
     89   Location& operator=(const Location& other) {
     90     value_ = other.value_;
     91     return *this;
     92   }
     93 
     94   bool IsConstant() const {
     95     return (value_ & kLocationConstantMask) == kConstant;
     96   }
     97 
     98   static Location ConstantLocation(HConstant* constant) {
     99     DCHECK(constant != nullptr);
    100     return Location(kConstant | reinterpret_cast<uintptr_t>(constant));
    101   }
    102 
    103   HConstant* GetConstant() const {
    104     DCHECK(IsConstant());
    105     return reinterpret_cast<HConstant*>(value_ & ~kLocationConstantMask);
    106   }
    107 
    108   bool IsValid() const {
    109     return value_ != kInvalid;
    110   }
    111 
    112   bool IsInvalid() const {
    113     return !IsValid();
    114   }
    115 
    116   // Empty location. Used if there the location should be ignored.
    117   static Location NoLocation() {
    118     return Location();
    119   }
    120 
    121   // Register locations.
    122   static Location RegisterLocation(int reg) {
    123     return Location(kRegister, reg);
    124   }
    125 
    126   static Location FpuRegisterLocation(int reg) {
    127     return Location(kFpuRegister, reg);
    128   }
    129 
    130   static Location RegisterPairLocation(int low, int high) {
    131     return Location(kRegisterPair, low << 16 | high);
    132   }
    133 
    134   static Location FpuRegisterPairLocation(int low, int high) {
    135     return Location(kFpuRegisterPair, low << 16 | high);
    136   }
    137 
    138   bool IsRegister() const {
    139     return GetKind() == kRegister;
    140   }
    141 
    142   bool IsFpuRegister() const {
    143     return GetKind() == kFpuRegister;
    144   }
    145 
    146   bool IsRegisterPair() const {
    147     return GetKind() == kRegisterPair;
    148   }
    149 
    150   bool IsFpuRegisterPair() const {
    151     return GetKind() == kFpuRegisterPair;
    152   }
    153 
    154   bool IsRegisterKind() const {
    155     return IsRegister() || IsFpuRegister() || IsRegisterPair() || IsFpuRegisterPair();
    156   }
    157 
    158   int reg() const {
    159     DCHECK(IsRegister() || IsFpuRegister());
    160     return GetPayload();
    161   }
    162 
    163   int low() const {
    164     DCHECK(IsPair());
    165     return GetPayload() >> 16;
    166   }
    167 
    168   int high() const {
    169     DCHECK(IsPair());
    170     return GetPayload() & 0xFFFF;
    171   }
    172 
    173   template <typename T>
    174   T AsRegister() const {
    175     DCHECK(IsRegister());
    176     return static_cast<T>(reg());
    177   }
    178 
    179   template <typename T>
    180   T AsFpuRegister() const {
    181     DCHECK(IsFpuRegister());
    182     return static_cast<T>(reg());
    183   }
    184 
    185   template <typename T>
    186   T AsRegisterPairLow() const {
    187     DCHECK(IsRegisterPair());
    188     return static_cast<T>(low());
    189   }
    190 
    191   template <typename T>
    192   T AsRegisterPairHigh() const {
    193     DCHECK(IsRegisterPair());
    194     return static_cast<T>(high());
    195   }
    196 
    197   template <typename T>
    198   T AsFpuRegisterPairLow() const {
    199     DCHECK(IsFpuRegisterPair());
    200     return static_cast<T>(low());
    201   }
    202 
    203   template <typename T>
    204   T AsFpuRegisterPairHigh() const {
    205     DCHECK(IsFpuRegisterPair());
    206     return static_cast<T>(high());
    207   }
    208 
    209   bool IsPair() const {
    210     return IsRegisterPair() || IsFpuRegisterPair();
    211   }
    212 
    213   Location ToLow() const {
    214     if (IsRegisterPair()) {
    215       return Location::RegisterLocation(low());
    216     } else if (IsFpuRegisterPair()) {
    217       return Location::FpuRegisterLocation(low());
    218     } else {
    219       DCHECK(IsDoubleStackSlot());
    220       return Location::StackSlot(GetStackIndex());
    221     }
    222   }
    223 
    224   Location ToHigh() const {
    225     if (IsRegisterPair()) {
    226       return Location::RegisterLocation(high());
    227     } else if (IsFpuRegisterPair()) {
    228       return Location::FpuRegisterLocation(high());
    229     } else {
    230       DCHECK(IsDoubleStackSlot());
    231       return Location::StackSlot(GetHighStackIndex(4));
    232     }
    233   }
    234 
    235   static uintptr_t EncodeStackIndex(intptr_t stack_index) {
    236     DCHECK(-kStackIndexBias <= stack_index);
    237     DCHECK(stack_index < kStackIndexBias);
    238     return static_cast<uintptr_t>(kStackIndexBias + stack_index);
    239   }
    240 
    241   static Location StackSlot(intptr_t stack_index) {
    242     uintptr_t payload = EncodeStackIndex(stack_index);
    243     Location loc(kStackSlot, payload);
    244     // Ensure that sign is preserved.
    245     DCHECK_EQ(loc.GetStackIndex(), stack_index);
    246     return loc;
    247   }
    248 
    249   bool IsStackSlot() const {
    250     return GetKind() == kStackSlot;
    251   }
    252 
    253   static Location DoubleStackSlot(intptr_t stack_index) {
    254     uintptr_t payload = EncodeStackIndex(stack_index);
    255     Location loc(kDoubleStackSlot, payload);
    256     // Ensure that sign is preserved.
    257     DCHECK_EQ(loc.GetStackIndex(), stack_index);
    258     return loc;
    259   }
    260 
    261   bool IsDoubleStackSlot() const {
    262     return GetKind() == kDoubleStackSlot;
    263   }
    264 
    265   intptr_t GetStackIndex() const {
    266     DCHECK(IsStackSlot() || IsDoubleStackSlot());
    267     // Decode stack index manually to preserve sign.
    268     return GetPayload() - kStackIndexBias;
    269   }
    270 
    271   intptr_t GetHighStackIndex(uintptr_t word_size) const {
    272     DCHECK(IsDoubleStackSlot());
    273     // Decode stack index manually to preserve sign.
    274     return GetPayload() - kStackIndexBias + word_size;
    275   }
    276 
    277   Kind GetKind() const {
    278     return IsConstant() ? kConstant : KindField::Decode(value_);
    279   }
    280 
    281   bool Equals(Location other) const {
    282     return value_ == other.value_;
    283   }
    284 
    285   bool Contains(Location other) const {
    286     if (Equals(other)) {
    287       return true;
    288     } else if (IsPair() || IsDoubleStackSlot()) {
    289       return ToLow().Equals(other) || ToHigh().Equals(other);
    290     }
    291     return false;
    292   }
    293 
    294   bool OverlapsWith(Location other) const {
    295     // Only check the overlapping case that can happen with our register allocation algorithm.
    296     bool overlap = Contains(other) || other.Contains(*this);
    297     if (kIsDebugBuild && !overlap) {
    298       // Note: These are also overlapping cases. But we are not able to handle them in
    299       // ParallelMoveResolverWithSwap. Make sure that we do not meet such case with our compiler.
    300       if ((IsPair() && other.IsPair()) || (IsDoubleStackSlot() && other.IsDoubleStackSlot())) {
    301         DCHECK(!Contains(other.ToLow()));
    302         DCHECK(!Contains(other.ToHigh()));
    303       }
    304     }
    305     return overlap;
    306   }
    307 
    308   const char* DebugString() const {
    309     switch (GetKind()) {
    310       case kInvalid: return "I";
    311       case kRegister: return "R";
    312       case kStackSlot: return "S";
    313       case kDoubleStackSlot: return "DS";
    314       case kUnallocated: return "U";
    315       case kConstant: return "C";
    316       case kFpuRegister: return "F";
    317       case kRegisterPair: return "RP";
    318       case kFpuRegisterPair: return "FP";
    319       case kDoNotUse5:  // fall-through
    320       case kDoNotUse9:
    321         LOG(FATAL) << "Should not use this location kind";
    322     }
    323     UNREACHABLE();
    324     return "?";
    325   }
    326 
    327   // Unallocated locations.
    328   enum Policy {
    329     kAny,
    330     kRequiresRegister,
    331     kRequiresFpuRegister,
    332     kSameAsFirstInput,
    333   };
    334 
    335   bool IsUnallocated() const {
    336     return GetKind() == kUnallocated;
    337   }
    338 
    339   static Location UnallocatedLocation(Policy policy) {
    340     return Location(kUnallocated, PolicyField::Encode(policy));
    341   }
    342 
    343   // Any free register is suitable to replace this unallocated location.
    344   static Location Any() {
    345     return UnallocatedLocation(kAny);
    346   }
    347 
    348   static Location RequiresRegister() {
    349     return UnallocatedLocation(kRequiresRegister);
    350   }
    351 
    352   static Location RequiresFpuRegister() {
    353     return UnallocatedLocation(kRequiresFpuRegister);
    354   }
    355 
    356   static Location RegisterOrConstant(HInstruction* instruction);
    357   static Location RegisterOrInt32LongConstant(HInstruction* instruction);
    358   static Location ByteRegisterOrConstant(int reg, HInstruction* instruction);
    359 
    360   // The location of the first input to the instruction will be
    361   // used to replace this unallocated location.
    362   static Location SameAsFirstInput() {
    363     return UnallocatedLocation(kSameAsFirstInput);
    364   }
    365 
    366   Policy GetPolicy() const {
    367     DCHECK(IsUnallocated());
    368     return PolicyField::Decode(GetPayload());
    369   }
    370 
    371   uintptr_t GetEncoding() const {
    372     return GetPayload();
    373   }
    374 
    375  private:
    376   // Number of bits required to encode Kind value.
    377   static constexpr uint32_t kBitsForKind = 4;
    378   static constexpr uint32_t kBitsForPayload = kBitsPerIntPtrT - kBitsForKind;
    379   static constexpr uintptr_t kLocationConstantMask = 0x3;
    380 
    381   explicit Location(uintptr_t value) : value_(value) {}
    382 
    383   Location(Kind kind, uintptr_t payload)
    384       : value_(KindField::Encode(kind) | PayloadField::Encode(payload)) {}
    385 
    386   uintptr_t GetPayload() const {
    387     return PayloadField::Decode(value_);
    388   }
    389 
    390   typedef BitField<Kind, 0, kBitsForKind> KindField;
    391   typedef BitField<uintptr_t, kBitsForKind, kBitsForPayload> PayloadField;
    392 
    393   // Layout for kUnallocated locations payload.
    394   typedef BitField<Policy, 0, 3> PolicyField;
    395 
    396   // Layout for stack slots.
    397   static const intptr_t kStackIndexBias =
    398       static_cast<intptr_t>(1) << (kBitsForPayload - 1);
    399 
    400   // Location either contains kind and payload fields or a tagged handle for
    401   // a constant locations. Values of enumeration Kind are selected in such a
    402   // way that none of them can be interpreted as a kConstant tag.
    403   uintptr_t value_;
    404 };
    405 std::ostream& operator<<(std::ostream& os, const Location::Kind& rhs);
    406 std::ostream& operator<<(std::ostream& os, const Location::Policy& rhs);
    407 
    408 class RegisterSet : public ValueObject {
    409  public:
    410   RegisterSet() : core_registers_(0), floating_point_registers_(0) {}
    411 
    412   void Add(Location loc) {
    413     if (loc.IsRegister()) {
    414       core_registers_ |= (1 << loc.reg());
    415     } else {
    416       DCHECK(loc.IsFpuRegister());
    417       floating_point_registers_ |= (1 << loc.reg());
    418     }
    419   }
    420 
    421   void Remove(Location loc) {
    422     if (loc.IsRegister()) {
    423       core_registers_ &= ~(1 << loc.reg());
    424     } else {
    425       DCHECK(loc.IsFpuRegister()) << loc;
    426       floating_point_registers_ &= ~(1 << loc.reg());
    427     }
    428   }
    429 
    430   bool ContainsCoreRegister(uint32_t id) {
    431     return Contains(core_registers_, id);
    432   }
    433 
    434   bool ContainsFloatingPointRegister(uint32_t id) {
    435     return Contains(floating_point_registers_, id);
    436   }
    437 
    438   static bool Contains(uint32_t register_set, uint32_t reg) {
    439     return (register_set & (1 << reg)) != 0;
    440   }
    441 
    442   size_t GetNumberOfRegisters() const {
    443     return __builtin_popcount(core_registers_) + __builtin_popcount(floating_point_registers_);
    444   }
    445 
    446   uint32_t GetCoreRegisters() const {
    447     return core_registers_;
    448   }
    449 
    450   uint32_t GetFloatingPointRegisters() const {
    451     return floating_point_registers_;
    452   }
    453 
    454  private:
    455   uint32_t core_registers_;
    456   uint32_t floating_point_registers_;
    457 
    458   DISALLOW_COPY_AND_ASSIGN(RegisterSet);
    459 };
    460 
    461 static constexpr bool kIntrinsified = true;
    462 
    463 /**
    464  * The code generator computes LocationSummary for each instruction so that
    465  * the instruction itself knows what code to generate: where to find the inputs
    466  * and where to place the result.
    467  *
    468  * The intent is to have the code for generating the instruction independent of
    469  * register allocation. A register allocator just has to provide a LocationSummary.
    470  */
    471 class LocationSummary : public ArenaObject<kArenaAllocMisc> {
    472  public:
    473   enum CallKind {
    474     kNoCall,
    475     kCallOnSlowPath,
    476     kCall
    477   };
    478 
    479   LocationSummary(HInstruction* instruction,
    480                   CallKind call_kind = kNoCall,
    481                   bool intrinsified = false);
    482 
    483   void SetInAt(uint32_t at, Location location) {
    484     DCHECK(inputs_.Get(at).IsUnallocated() || inputs_.Get(at).IsInvalid());
    485     inputs_.Put(at, location);
    486   }
    487 
    488   Location InAt(uint32_t at) const {
    489     return inputs_.Get(at);
    490   }
    491 
    492   size_t GetInputCount() const {
    493     return inputs_.Size();
    494   }
    495 
    496   void SetOut(Location location, Location::OutputOverlap overlaps = Location::kOutputOverlap) {
    497     DCHECK(output_.IsInvalid());
    498     output_overlaps_ = overlaps;
    499     output_ = location;
    500   }
    501 
    502   void UpdateOut(Location location) {
    503     // There are two reasons for updating an output:
    504     // 1) Parameters, where we only know the exact stack slot after
    505     //    doing full register allocation.
    506     // 2) Unallocated location.
    507     DCHECK(output_.IsStackSlot() || output_.IsDoubleStackSlot() || output_.IsUnallocated());
    508     output_ = location;
    509   }
    510 
    511   void AddTemp(Location location) {
    512     temps_.Add(location);
    513   }
    514 
    515   Location GetTemp(uint32_t at) const {
    516     return temps_.Get(at);
    517   }
    518 
    519   void SetTempAt(uint32_t at, Location location) {
    520     DCHECK(temps_.Get(at).IsUnallocated() || temps_.Get(at).IsInvalid());
    521     temps_.Put(at, location);
    522   }
    523 
    524   size_t GetTempCount() const {
    525     return temps_.Size();
    526   }
    527 
    528   Location Out() const { return output_; }
    529 
    530   bool CanCall() const { return call_kind_ != kNoCall; }
    531   bool WillCall() const { return call_kind_ == kCall; }
    532   bool OnlyCallsOnSlowPath() const { return call_kind_ == kCallOnSlowPath; }
    533   bool NeedsSafepoint() const { return CanCall(); }
    534 
    535   void SetStackBit(uint32_t index) {
    536     stack_mask_->SetBit(index);
    537   }
    538 
    539   void ClearStackBit(uint32_t index) {
    540     stack_mask_->ClearBit(index);
    541   }
    542 
    543   void SetRegisterBit(uint32_t reg_id) {
    544     register_mask_ |= (1 << reg_id);
    545   }
    546 
    547   uint32_t GetRegisterMask() const {
    548     return register_mask_;
    549   }
    550 
    551   bool RegisterContainsObject(uint32_t reg_id) {
    552     return RegisterSet::Contains(register_mask_, reg_id);
    553   }
    554 
    555   void AddLiveRegister(Location location) {
    556     live_registers_.Add(location);
    557   }
    558 
    559   BitVector* GetStackMask() const {
    560     return stack_mask_;
    561   }
    562 
    563   RegisterSet* GetLiveRegisters() {
    564     return &live_registers_;
    565   }
    566 
    567   size_t GetNumberOfLiveRegisters() const {
    568     return live_registers_.GetNumberOfRegisters();
    569   }
    570 
    571   bool OutputUsesSameAs(uint32_t input_index) const {
    572     return (input_index == 0)
    573         && output_.IsUnallocated()
    574         && (output_.GetPolicy() == Location::kSameAsFirstInput);
    575   }
    576 
    577   bool IsFixedInput(uint32_t input_index) const {
    578     Location input = inputs_.Get(input_index);
    579     return input.IsRegister()
    580         || input.IsFpuRegister()
    581         || input.IsPair()
    582         || input.IsStackSlot()
    583         || input.IsDoubleStackSlot();
    584   }
    585 
    586   bool OutputCanOverlapWithInputs() const {
    587     return output_overlaps_ == Location::kOutputOverlap;
    588   }
    589 
    590   bool Intrinsified() const {
    591     return intrinsified_;
    592   }
    593 
    594  private:
    595   GrowableArray<Location> inputs_;
    596   GrowableArray<Location> temps_;
    597   // Whether the output overlaps with any of the inputs. If it overlaps, then it cannot
    598   // share the same register as the inputs.
    599   Location::OutputOverlap output_overlaps_;
    600   Location output_;
    601   const CallKind call_kind_;
    602 
    603   // Mask of objects that live in the stack.
    604   BitVector* stack_mask_;
    605 
    606   // Mask of objects that live in register.
    607   uint32_t register_mask_;
    608 
    609   // Registers that are in use at this position.
    610   RegisterSet live_registers_;
    611 
    612   // Whether these are locations for an intrinsified call.
    613   const bool intrinsified_;
    614 
    615   ART_FRIEND_TEST(RegisterAllocatorTest, ExpectedInRegisterHint);
    616   ART_FRIEND_TEST(RegisterAllocatorTest, SameAsFirstInputHint);
    617   DISALLOW_COPY_AND_ASSIGN(LocationSummary);
    618 };
    619 
    620 }  // namespace art
    621 
    622 #endif  // ART_COMPILER_OPTIMIZING_LOCATIONS_H_
    623