tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

SimpleAllocator.h (14285B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
      2 * vim: set ts=8 sts=2 et sw=2 tw=80:
      3 * This Source Code Form is subject to the terms of the Mozilla Public
      4 * License, v. 2.0. If a copy of the MPL was not distributed with this
      5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      6 
      7 #ifndef jit_SimpleAllocator_h
      8 #define jit_SimpleAllocator_h
      9 
     10 #include "mozilla/Array.h"
     11 #include "mozilla/Attributes.h"
     12 #include "mozilla/Maybe.h"
     13 
     14 #include "jit/RegisterAllocator.h"
     15 #include "jit/SparseBitSet.h"
     16 #include "jit/StackSlotAllocator.h"
     17 
     18 namespace js {
     19 namespace jit {
     20 
     21 class MOZ_STACK_CLASS SimpleAllocator : protected RegisterAllocator {
     22 public:
     23  using IsStackAllocated = std::true_type;
     24 
     25 private:
     26  // Information about a virtual register.
     27  class VirtualRegister {
     28    // The definition and the id of the LIR instruction that contains it.
     29    LDefinition* def_;
     30    uint32_t insId_;
     31 
     32    // The id of the LIR instruction that's considered the 'last use' of this
     33    // virtual register. After this instruction we free any register or stack
     34    // slot allocated for this virtual register and we mark this virtual
     35    // register as dead.
     36    uint32_t lastUseInsId_;
     37 
     38    // Either UINT32_MAX (meaning no stack slot has been allocated) or the stack
     39    // slot offset and width of a slot we allocated for this virtual register.
     40    static constexpr uint32_t NoStackSlotAndWidth = UINT32_MAX;
     41    uint32_t stackSlotAndWidth_ = NoStackSlotAndWidth;
     42 
     43    // If this virtual register has fixed register uses, we use this register
     44    // hint when allocating registers to help avoid moves.
     45    // This has three states:
     46    // - Nothing: we didn't see any fixed register uses.
     47    // - Some(valid AnyRegister): there are fixed register uses and they all use
     48    //   this register.
     49    // - Some(Invalid AnyRegister): there are multiple fixed register uses for
     50    //   different registers and we gave up on assigning a register hint.
     51    mozilla::Maybe<AnyRegister> fixedUseHint_;
     52 
     53    // The index in the allocator's allocatedRegs_ vector, or NoRegisterIndex if
     54    // this vreg has no allocated register.
     55    //
     56    // In some uncommon cases a vreg can have multiple registers assigned to it
     57    // and in this case the index is for one of these registers.
     58    // See hasMultipleRegsForVreg_.
     59    static constexpr size_t NoRegisterIndex = UINT8_MAX;
     60    uint8_t registerIndex_ = NoRegisterIndex;
     61 
     62    // Assert registerIndex_ fits in a byte. There must be at most one
     63    // AllocatedRegister entry for each AnyRegister value.
     64    static_assert(sizeof(AnyRegister) == sizeof(registerIndex_));
     65    static_assert(AnyRegister::Invalid == NoRegisterIndex);
     66 
     67    // Whether this virtual register is for a Temp.
     68    bool isTemp_ : 1;
     69 
     70    // Whether this virtual register has a stack location. This location is
     71    // either a stack slot we allocated (see stackSlotAndWidth_) or this virtual
     72    // register came with an assigned stack location (for example for stack
     73    // arguments).
     74    bool hasStackLocation_ : 1;
     75 
     76    // Whether this virtual register is for a GC type that needs to be added to
     77    // safepoints.
     78    bool isGCType_ : 1;
     79 
     80    // Whether this virtual register is dead. This is set after allocating
     81    // registers for the lastUseInsId_ instruction.
     82    bool isDead_ : 1;
     83 
     84   public:
     85    VirtualRegister() = default;
     86 
     87    VirtualRegister(VirtualRegister&) = delete;
     88    void operator=(VirtualRegister&) = delete;
     89 
     90    void init(LNode* ins, LDefinition* def, bool isTemp) {
     91      def_ = def;
     92      insId_ = ins->id();
     93      lastUseInsId_ = ins->id();
     94      isTemp_ = isTemp;
     95      hasStackLocation_ = false;
     96      isGCType_ = def->isSafepointGCType(ins);
     97      isDead_ = false;
     98    }
     99 
    100    LDefinition* def() const { return def_; }
    101    uint32_t insId() const { return insId_; }
    102    uint32_t lastUseInsId() const { return lastUseInsId_; }
    103 
    104    uint8_t registerIndex() const {
    105      MOZ_ASSERT(hasRegister());
    106      return registerIndex_;
    107    }
    108    bool hasRegister() const {
    109      MOZ_ASSERT(!isDead());
    110      return registerIndex_ != NoRegisterIndex;
    111    }
    112    void setRegisterIndex(uint8_t registerIndex) {
    113      MOZ_ASSERT(!isDead());
    114      MOZ_ASSERT(registerIndex < NoRegisterIndex);
    115      registerIndex_ = registerIndex;
    116    }
    117    void clearRegisterIndex() {
    118      MOZ_ASSERT(!isDead());
    119      registerIndex_ = NoRegisterIndex;
    120    }
    121 
    122    LAllocation stackLocation() const {
    123      MOZ_ASSERT(hasStackLocation());
    124      if (hasAllocatedStackSlot()) {
    125        return LStackSlot(stackSlot());
    126      }
    127      MOZ_ASSERT(def()->policy() == LDefinition::FIXED);
    128      MOZ_ASSERT(!def()->output()->isAnyRegister());
    129      return *def()->output();
    130    }
    131    void setHasStackLocation() {
    132      MOZ_ASSERT(!isDead());
    133      MOZ_ASSERT(!isTemp());
    134      MOZ_ASSERT(!hasStackLocation_);
    135      MOZ_ASSERT(stackSlotAndWidth_ == NoStackSlotAndWidth);
    136      hasStackLocation_ = true;
    137    }
    138 
    139    bool hasAllocatedStackSlot() const {
    140      MOZ_ASSERT(!isDead());
    141      MOZ_ASSERT_IF(stackSlotAndWidth_ != NoStackSlotAndWidth,
    142                    hasStackLocation_);
    143      return stackSlotAndWidth_ != NoStackSlotAndWidth;
    144    }
    145    LStackSlot::SlotAndWidth stackSlot() const {
    146      MOZ_ASSERT(hasAllocatedStackSlot());
    147      return LStackSlot::SlotAndWidth::fromData(stackSlotAndWidth_);
    148    }
    149    void setAllocatedStackSlot(LStackSlot::SlotAndWidth slot) {
    150      setHasStackLocation();
    151      MOZ_ASSERT(stackSlotAndWidth_ == NoStackSlotAndWidth);
    152      MOZ_ASSERT(slot.data() != NoStackSlotAndWidth);
    153      stackSlotAndWidth_ = slot.data();
    154    }
    155 
    156    void markDead() {
    157      MOZ_ASSERT(!isDead());
    158      isDead_ = true;
    159    }
    160 
    161    mozilla::Maybe<AnyRegister> fixedUseHint() const { return fixedUseHint_; }
    162    void setFixedUseHint(AnyRegister reg) {
    163      fixedUseHint_ = mozilla::Some(reg);
    164    }
    165 
    166    bool hasStackLocation() const { return hasStackLocation_; }
    167    bool isGCType() const { return isGCType_; }
    168    bool isTemp() const { return isTemp_; }
    169    bool isDead() const { return isDead_; }
    170 
    171    void updateLastUseId(uint32_t useInsId) {
    172      MOZ_ASSERT(!isTemp());
    173      MOZ_ASSERT(useInsId > insId_);
    174      if (useInsId > lastUseInsId_) {
    175        lastUseInsId_ = useInsId;
    176      }
    177    }
    178  };
    179 
    180  // Information about virtual registers.
    181  Vector<VirtualRegister, 0, JitAllocPolicy> vregs_;
    182 
    183  // Information about an allocated register.
    184  class AllocatedRegister {
    185    static constexpr size_t VregBits = 24;
    186    static constexpr size_t RegisterBits = 8;
    187 
    188    // The virtual register.
    189    uint32_t vregId_ : VregBits;
    190 
    191    // The AnyRegister code. We don't use AnyRegister directly because the
    192    // compiler adds additional padding bytes on Windows if we do that.
    193    uint32_t reg_ : RegisterBits;
    194 
    195    // Id of the last LIR instruction that used this allocated register. Used
    196    // for eviction heuristics.
    197    uint32_t lastUsedAtInsId_;
    198 
    199    static_assert(MAX_VIRTUAL_REGISTERS <= (1 << VregBits) - 1);
    200    static_assert(sizeof(AnyRegister::Code) * 8 == RegisterBits);
    201 
    202   public:
    203    AllocatedRegister(uint32_t vreg, AnyRegister reg, uint32_t lastUsedAtInsId)
    204        : vregId_(vreg), reg_(reg.code()), lastUsedAtInsId_(lastUsedAtInsId) {}
    205 
    206    uint32_t vregId() const { return vregId_; }
    207    AnyRegister reg() const { return AnyRegister::FromCode(reg_); }
    208    uint32_t lastUsedAtInsId() const { return lastUsedAtInsId_; }
    209    void setLastUsedAtInsId(uint32_t insId) {
    210      MOZ_ASSERT(insId >= lastUsedAtInsId_);
    211      lastUsedAtInsId_ = insId;
    212    }
    213  };
    214  static_assert(sizeof(AllocatedRegister) == 2 * sizeof(uint32_t),
    215                "AllocatedRegister should not have unnecessary padding");
    216 
    217  // Information about allocated physical registers.
    218  using AllocatedRegisterVector =
    219      Vector<AllocatedRegister, 16, BackgroundSystemAllocPolicy>;
    220  AllocatedRegisterVector allocatedRegs_;
    221  AllocatableRegisterSet availableRegs_;
    222 
    223  // Whether there might be multiple entries in allocatedRegs_ for the same
    224  // vreg. This can happen for instance if an instruction has multiple fixed
    225  // register uses for the same vreg.
    226  //
    227  // This is uncommon and we try to avoid it, but if it does happen we fix
    228  // it up at the end of allocateForInstruction.
    229  bool hasMultipleRegsForVreg_ = false;
    230 
    231  // All registers allocated for the current LIR instruction.
    232  AllocatableRegisterSet currentInsRegs_;
    233 
    234  // Like currentInsRegs_, but does not include registers that are only used
    235  // for at-start uses.
    236  AllocatableRegisterSet currentInsRegsNotAtStart_;
    237 
    238  // Registers required for fixed outputs/temps of the current LIR instruction.
    239  AllocatableRegisterSet fixedTempRegs_;
    240  AllocatableRegisterSet fixedOutputAndTempRegs_;
    241 
    242  // The set of live GC things at the start of each basic block. Although the
    243  // VirtualRegBitSet may contain malloced memory, all are owned by the
    244  // SimpleAllocator whose destructor will destroy them.
    245  using VirtualRegBitSet =
    246      SparseBitSet<BackgroundSystemAllocPolicy, SimpleAllocator>;
    247  Vector<VirtualRegBitSet, 0, JitAllocPolicy> liveGCIn_;
    248 
    249  // Vector sorted by instructionId in descending order. This is used by
    250  // freeDeadVregsAfterInstruction to mark virtual registers as dead after their
    251  // last use.
    252  struct VregLastUse {
    253    uint32_t instructionId;
    254    uint32_t vregId;
    255    VregLastUse(uint32_t instructionId, uint32_t vregId)
    256        : instructionId(instructionId), vregId(vregId) {}
    257  };
    258  Vector<VregLastUse, 0, JitAllocPolicy> vregLastUses_;
    259 
    260  // Vector used for spilling instruction outputs that are used across blocks.
    261  Vector<LDefinition*, 4, BackgroundSystemAllocPolicy> eagerSpillOutputs_;
    262 
    263  // Allocator used to allocate and free stack slots.
    264  StackSlotAllocator stackSlotAllocator_;
    265 
    266  // Register state for a small number of previous blocks. Blocks with a single
    267  // predecessor block can optionally reuse this state.
    268  //
    269  // BlockStateLength should be small enough so that iterating over the array is
    270  // very cheap. It's currently 4 and this was sufficient for a hit rate of
    271  // 88.6% on a very large Wasm module.
    272  static constexpr size_t BlockStateLength = 4;
    273  struct BlockState {
    274    uint32_t blockIndex = UINT32_MAX;
    275    AllocatedRegisterVector allocatedRegs;
    276    AllocatableRegisterSet availableRegs;
    277  };
    278  mozilla::Array<BlockState, BlockStateLength> blockStates_;
    279  size_t nextBlockStateIndex_ = 0;
    280 
    281  // Data used to insert a move for the input of a MUST_REUSE_INPUT definition.
    282  struct ReusedInputReg {
    283    LAllocation* source;
    284    AnyRegister dest;
    285    LDefinition::Type type;
    286    ReusedInputReg(LAllocation* source, AnyRegister dest,
    287                   LDefinition::Type type)
    288        : source(source), dest(dest), type(type) {}
    289  };
    290  Vector<ReusedInputReg, 4, BackgroundSystemAllocPolicy> reusedInputs_;
    291 
    292  enum class AllocationKind { UseAtStart, Output, UseOrTemp };
    293 
    294  [[nodiscard]] bool addAllocatedReg(LInstruction* ins, uint32_t vregId,
    295                                     bool usedAtStart, AnyRegister reg) {
    296    currentInsRegs_.addUnchecked(reg);
    297    if (!usedAtStart) {
    298      currentInsRegsNotAtStart_.addUnchecked(reg);
    299    }
    300    availableRegs_.take(reg);
    301    MOZ_ASSERT_IF(vregs_[vregId].hasRegister(), hasMultipleRegsForVreg_);
    302    vregs_[vregId].setRegisterIndex(allocatedRegs_.length());
    303    return allocatedRegs_.emplaceBack(vregId, reg, ins->id());
    304  }
    305  void markUseOfAllocatedReg(LInstruction* ins, AllocatedRegister& allocated,
    306                             bool usedAtStart) {
    307    MOZ_ASSERT(!availableRegs_.has(allocated.reg()));
    308    allocated.setLastUsedAtInsId(ins->id());
    309    currentInsRegs_.addUnchecked(allocated.reg());
    310    if (!usedAtStart) {
    311      currentInsRegsNotAtStart_.addUnchecked(allocated.reg());
    312    }
    313  }
    314 
    315  [[nodiscard]] bool init();
    316  [[nodiscard]] bool analyzeLiveness();
    317  [[nodiscard]] bool allocateRegisters();
    318 
    319  void removeAllocatedRegisterAtIndex(size_t index);
    320 
    321  [[nodiscard]] bool tryReuseRegistersFromPredecessor(MBasicBlock* block);
    322  void saveAndClearAllocatedRegisters(MBasicBlock* block);
    323 
    324  void freeDeadVregsAfterInstruction(VirtualRegBitSet& liveGC, LNode* ins);
    325 
    326  [[nodiscard]] bool allocateForBlockEnd(LBlock* block, LInstruction* ins);
    327 
    328  LAllocation ensureStackLocation(uint32_t vregId);
    329  LAllocation registerOrStackLocation(LInstruction* ins, uint32_t vregId,
    330                                      bool trackRegUse);
    331 
    332  [[nodiscard]] bool spillRegister(LInstruction* ins,
    333                                   AllocatedRegister allocated);
    334 
    335  [[nodiscard]] bool evictRegister(LInstruction* ins, AnyRegister reg);
    336 
    337  void scanDefinition(LInstruction* ins, LDefinition* def, bool isTemp);
    338 
    339  [[nodiscard]] bool allocateForNonFixedDefOrUse(LInstruction* ins,
    340                                                 uint32_t vregId,
    341                                                 AllocationKind kind,
    342                                                 AnyRegister* reg);
    343  [[nodiscard]] bool allocateForFixedUse(LInstruction* ins, const LUse* use,
    344                                         AnyRegister* reg);
    345  [[nodiscard]] bool allocateForRegisterUse(LInstruction* ins, const LUse* use,
    346                                            AnyRegister* reg);
    347 
    348  [[nodiscard]] bool allocateForDefinition(uint32_t blockLastId,
    349                                           LInstruction* ins, LDefinition* def,
    350                                           bool isTemp);
    351  [[nodiscard]] bool allocateForInstruction(VirtualRegBitSet& liveGC,
    352                                            uint32_t blockLastId,
    353                                            LInstruction* ins);
    354 
    355  [[nodiscard]] bool addLiveRegisterToSafepoint(LSafepoint* safepoint,
    356                                                AllocatedRegister allocated);
    357  [[nodiscard]] bool populateSafepoint(VirtualRegBitSet& liveGC,
    358                                       LInstruction* ins,
    359                                       LSafepoint* safepoint);
    360 
    361  void assertValidRegisterStateBeforeInstruction() const;
    362 
    363 public:
    364  SimpleAllocator(MIRGenerator* mir, LIRGenerator* lir, LIRGraph& graph)
    365      : RegisterAllocator(mir, lir, graph),
    366        vregs_(mir->alloc()),
    367        liveGCIn_(mir->alloc()),
    368        vregLastUses_(mir->alloc()) {}
    369 
    370  [[nodiscard]] bool go();
    371 };
    372 
    373 }  // namespace jit
    374 }  // namespace js
    375 
    376 #endif /* jit_SimpleAllocator_h */