tor-browser

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

RegisterAllocator.h (10046B)

      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_RegisterAllocator_h
      8 #define jit_RegisterAllocator_h
      9 
     10 #include "mozilla/MathAlgorithms.h"
     11 
     12 #include <compare>  // std::strong_ordering
     13 
     14 #include "jit/LIR.h"
     15 #include "jit/MIRGenerator.h"
     16 #include "jit/MIRGraph.h"
     17 
     18 // Generic structures and functions for use by register allocators.
     19 
     20 namespace js {
     21 namespace jit {
     22 
     23 class LIRGenerator;
     24 
     25 #ifdef DEBUG
     26 // Structure for running a liveness analysis on a finished register allocation.
     27 // This analysis can be used for two purposes:
     28 //
     29 // - Check the integrity of the allocation, i.e. that the reads and writes of
     30 //   physical values preserve the semantics of the original virtual registers.
     31 //
     32 // - Populate safepoints with live registers, GC thing and value data, to
     33 //   streamline the process of prototyping new allocators.
     34 struct AllocationIntegrityState {
     35  explicit AllocationIntegrityState(LIRGraph& graph) : graph(graph) {}
     36 
     37  // Record all virtual registers in the graph. This must be called before
     38  // register allocation, to pick up the original LUses.
     39  [[nodiscard]] bool record();
     40 
     41  // Perform the liveness analysis on the graph, and assert on an invalid
     42  // allocation. This must be called after register allocation, to pick up
     43  // all assigned physical values.
     44  [[nodiscard]] bool check();
     45 
     46 private:
     47  LIRGraph& graph;
     48 
     49  // For all instructions and phis in the graph, keep track of the virtual
     50  // registers for all inputs and outputs of the nodes. These are overwritten
     51  // in place during register allocation. This information is kept on the
     52  // side rather than in the instructions and phis themselves to avoid
     53  // debug-builds-only bloat in the size of the involved structures.
     54 
     55  struct InstructionInfo {
     56    Vector<LAllocation, 2, SystemAllocPolicy> inputs;
     57    Vector<LDefinition, 0, SystemAllocPolicy> temps;
     58    Vector<LDefinition, 1, SystemAllocPolicy> outputs;
     59 
     60    InstructionInfo() = default;
     61 
     62    InstructionInfo(const InstructionInfo& o) {
     63      AutoEnterOOMUnsafeRegion oomUnsafe;
     64      if (!inputs.appendAll(o.inputs) || !temps.appendAll(o.temps) ||
     65          !outputs.appendAll(o.outputs)) {
     66        oomUnsafe.crash("InstructionInfo::InstructionInfo");
     67      }
     68    }
     69  };
     70  Vector<InstructionInfo, 0, SystemAllocPolicy> instructions;
     71 
     72  struct BlockInfo {
     73    Vector<InstructionInfo, 5, SystemAllocPolicy> phis;
     74    BlockInfo() = default;
     75    BlockInfo(const BlockInfo& o) {
     76      AutoEnterOOMUnsafeRegion oomUnsafe;
     77      if (!phis.appendAll(o.phis)) {
     78        oomUnsafe.crash("BlockInfo::BlockInfo");
     79      }
     80    }
     81  };
     82  Vector<BlockInfo, 0, SystemAllocPolicy> blocks;
     83 
     84  Vector<LDefinition*, 20, SystemAllocPolicy> virtualRegisters;
     85 
     86  // Describes a correspondence that should hold at the end of a block.
     87  // The value which was written to vreg in the original LIR should be
     88  // physically stored in alloc after the register allocation.
     89  struct IntegrityItem {
     90    LBlock* block;
     91    uint32_t vreg;
     92    LAllocation alloc;
     93 
     94    // Order of insertion into seen, for sorting.
     95    uint32_t index;
     96 
     97    using Lookup = IntegrityItem;
     98    static HashNumber hash(const IntegrityItem& item) {
     99      HashNumber hash = item.alloc.hash();
    100      hash = mozilla::RotateLeft(hash, 4) ^ item.vreg;
    101      hash = mozilla::RotateLeft(hash, 4) ^ HashNumber(item.block->mir()->id());
    102      return hash;
    103    }
    104    static bool match(const IntegrityItem& one, const IntegrityItem& two) {
    105      return one.block == two.block && one.vreg == two.vreg &&
    106             one.alloc == two.alloc;
    107    }
    108  };
    109 
    110  // Items still to be processed.
    111  Vector<IntegrityItem, 10, SystemAllocPolicy> worklist;
    112 
    113  // Set of all items that have already been processed.
    114  using IntegrityItemSet =
    115      HashSet<IntegrityItem, IntegrityItem, SystemAllocPolicy>;
    116  IntegrityItemSet seen;
    117 
    118  [[nodiscard]] bool checkIntegrity(LBlock* block, LInstruction* ins,
    119                                    uint32_t vreg, LAllocation alloc);
    120  void checkSafepointAllocation(LInstruction* ins, uint32_t vreg,
    121                                LAllocation alloc);
    122  [[nodiscard]] bool addPredecessor(LBlock* block, uint32_t vreg,
    123                                    LAllocation alloc);
    124 
    125  void dump();
    126 };
    127 #endif  // DEBUG
    128 
    129 // Represents with better-than-instruction precision a position in the
    130 // instruction stream.
    131 //
    132 // An issue comes up when performing register allocation as to how to represent
    133 // information such as "this register is only needed for the input of
    134 // this instruction, it can be clobbered in the output". Just having ranges
    135 // of instruction IDs is insufficiently expressive to denote all possibilities.
    136 // This class solves this issue by associating an extra bit with the instruction
    137 // ID which indicates whether the position is the input half or output half of
    138 // an instruction.
    139 class CodePosition {
    140 private:
    141  constexpr explicit CodePosition(uint32_t bits) : bits_(bits) {}
    142 
    143  static const unsigned int INSTRUCTION_SHIFT = 1;
    144  static const unsigned int SUBPOSITION_MASK = 1;
    145  uint32_t bits_;
    146 
    147 public:
    148  static const CodePosition MAX;
    149  static const CodePosition MIN;
    150 
    151  // This is the half of the instruction this code position represents, as
    152  // described in the huge comment above.
    153  enum SubPosition { INPUT, OUTPUT };
    154 
    155  constexpr CodePosition() : bits_(0) {}
    156 
    157  CodePosition(uint32_t instruction, SubPosition where) {
    158    MOZ_ASSERT(instruction < 0x80000000u);
    159    MOZ_ASSERT(((uint32_t)where & SUBPOSITION_MASK) == (uint32_t)where);
    160    bits_ = (instruction << INSTRUCTION_SHIFT) | (uint32_t)where;
    161  }
    162 
    163  uint32_t ins() const { return bits_ >> INSTRUCTION_SHIFT; }
    164 
    165  uint32_t bits() const { return bits_; }
    166 
    167  SubPosition subpos() const { return (SubPosition)(bits_ & SUBPOSITION_MASK); }
    168 
    169  constexpr auto operator<=>(const CodePosition& other) const = default;
    170 
    171  uint32_t operator-(CodePosition other) const {
    172    MOZ_ASSERT(bits_ >= other.bits_);
    173    return bits_ - other.bits_;
    174  }
    175 
    176  CodePosition previous() const {
    177    MOZ_ASSERT(*this != MIN);
    178    return CodePosition(bits_ - 1);
    179  }
    180  CodePosition next() const {
    181    MOZ_ASSERT(*this != MAX);
    182    return CodePosition(bits_ + 1);
    183  }
    184 };
    185 
    186 // Structure to track all moves inserted next to instructions in a graph.
    187 class InstructionDataMap {
    188  FixedList<LNode*> insData_;
    189 
    190 public:
    191  InstructionDataMap() {}
    192 
    193  [[nodiscard]] bool init(MIRGenerator* gen, uint32_t numInstructions) {
    194    if (!insData_.init(gen->alloc(), numInstructions)) {
    195      return false;
    196    }
    197    memset(&insData_[0], 0, sizeof(LNode*) * numInstructions);
    198    return true;
    199  }
    200 
    201  LNode*& operator[](CodePosition pos) { return operator[](pos.ins()); }
    202  LNode* const& operator[](CodePosition pos) const {
    203    return operator[](pos.ins());
    204  }
    205  LNode*& operator[](uint32_t ins) { return insData_[ins]; }
    206  LNode* const& operator[](uint32_t ins) const { return insData_[ins]; }
    207 };
    208 
    209 // Common superclass for register allocators.
    210 class RegisterAllocator {
    211  void operator=(const RegisterAllocator&) = delete;
    212  RegisterAllocator(const RegisterAllocator&) = delete;
    213 
    214 protected:
    215  // Context
    216  MIRGenerator* mir;
    217  LIRGenerator* lir;
    218  LIRGraph& graph;
    219 
    220  // Pool of all registers that should be considered allocateable
    221  AllocatableRegisterSet allRegisters_;
    222 
    223  RegisterAllocator(MIRGenerator* mir, LIRGenerator* lir, LIRGraph& graph)
    224      : mir(mir), lir(lir), graph(graph), allRegisters_(RegisterSet::All()) {
    225    MOZ_ASSERT(!allRegisters_.has(FramePointer));
    226    if (mir->compilingWasm()) {
    227      takeWasmRegisters(allRegisters_);
    228    }
    229  }
    230 
    231  TempAllocator& alloc() const { return mir->alloc(); }
    232 
    233  CodePosition outputOf(const LNode* ins) const {
    234    return ins->isPhi() ? outputOf(ins->toPhi())
    235                        : outputOf(ins->toInstruction());
    236  }
    237  CodePosition outputOf(const LPhi* ins) const {
    238    // All phis in a block write their outputs after all of them have
    239    // read their inputs. Consequently, it doesn't make sense to talk
    240    // about code positions in the middle of a series of phis.
    241    LBlock* block = ins->block();
    242    return CodePosition(block->getPhi(block->numPhis() - 1)->id(),
    243                        CodePosition::OUTPUT);
    244  }
    245  CodePosition outputOf(const LInstruction* ins) const {
    246    return CodePosition(ins->id(), CodePosition::OUTPUT);
    247  }
    248  CodePosition inputOf(const LNode* ins) const {
    249    return ins->isPhi() ? inputOf(ins->toPhi()) : inputOf(ins->toInstruction());
    250  }
    251  CodePosition inputOf(const LPhi* ins) const {
    252    // All phis in a block read their inputs before any of them write their
    253    // outputs. Consequently, it doesn't make sense to talk about code
    254    // positions in the middle of a series of phis.
    255    return CodePosition(ins->block()->getPhi(0)->id(), CodePosition::INPUT);
    256  }
    257  CodePosition inputOf(const LInstruction* ins) const {
    258    return CodePosition(ins->id(), CodePosition::INPUT);
    259  }
    260 
    261  LMoveGroup* getInputMoveGroup(LInstruction* ins);
    262  LMoveGroup* getFixReuseMoveGroup(LInstruction* ins);
    263  LMoveGroup* getMoveGroupAfter(LInstruction* ins);
    264 
    265  void dumpInstructions(const char* who);
    266 
    267 public:
    268  template <typename TakeableSet>
    269  static void takeWasmRegisters(TakeableSet& regs) {
    270 #if defined(JS_CODEGEN_X64) || defined(JS_CODEGEN_ARM) ||      \
    271    defined(JS_CODEGEN_ARM64) || defined(JS_CODEGEN_MIPS64) || \
    272    defined(JS_CODEGEN_LOONG64) || defined(JS_CODEGEN_RISCV64)
    273    regs.take(HeapReg);
    274 #endif
    275    MOZ_ASSERT(!regs.has(FramePointer));
    276  }
    277 };
    278 
    279 static inline AnyRegister GetFixedRegister(const LDefinition* def,
    280                                           const LUse* use) {
    281  return def->isFloatReg()
    282             ? AnyRegister(FloatRegister::FromCode(use->registerCode()))
    283             : AnyRegister(Register::FromCode(use->registerCode()));
    284 }
    285 
    286 }  // namespace jit
    287 }  // namespace js
    288 
    289 #endif /* jit_RegisterAllocator_h */