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_shared_IonAssemblerBufferWithConstantPools_h 8 #define jit_shared_IonAssemblerBufferWithConstantPools_h 9 10 #include "mozilla/CheckedInt.h" 11 #include "mozilla/MathAlgorithms.h" 12 13 #include <algorithm> 14 15 #include "jit/JitSpewer.h" 16 #include "jit/shared/IonAssemblerBuffer.h" 17 18 // [SMDOC] JIT AssemblerBuffer constant pooling (ARM/ARM64/MIPS) 19 // 20 // This code extends the AssemblerBuffer to support the pooling of values loaded 21 // using program-counter relative addressing modes. This is necessary with the 22 // ARM instruction set because it has a fixed instruction size that can not 23 // encode all values as immediate arguments in instructions. Pooling the values 24 // allows the values to be placed in large chunks which minimizes the number of 25 // forced branches around them in the code. This is used for loading floating 26 // point constants, for loading 32 bit constants on the ARMv6, for absolute 27 // branch targets, and in future will be needed for large branches on the ARMv6. 28 // 29 // For simplicity of the implementation, the constant pools are always placed 30 // after the loads referencing them. When a new constant pool load is added to 31 // the assembler buffer, a corresponding pool entry is added to the current 32 // pending pool. The finishPool() method copies the current pending pool entries 33 // into the assembler buffer at the current offset and patches the pending 34 // constant pool load instructions. 35 // 36 // Before inserting instructions or pool entries, it is necessary to determine 37 // if doing so would place a pending pool entry out of reach of an instruction, 38 // and if so then the pool must firstly be dumped. With the allocation algorithm 39 // used below, the recalculation of all the distances between instructions and 40 // their pool entries can be avoided by noting that there will be a limiting 41 // instruction and pool entry pair that does not change when inserting more 42 // instructions. Adding more instructions makes the same increase to the 43 // distance, between instructions and their pool entries, for all such 44 // pairs. This pair is recorded as the limiter, and it is updated when new pool 45 // entries are added, see updateLimiter() 46 // 47 // The pools consist of: a guard instruction that branches around the pool, a 48 // header word that helps identify a pool in the instruction stream, and then 49 // the pool entries allocated in units of words. The guard instruction could be 50 // omitted if control does not reach the pool, and this is referred to as a 51 // natural guard below, but for simplicity the guard branch is always 52 // emitted. The pool header is an identifiable word that in combination with the 53 // guard uniquely identifies a pool in the instruction stream. The header also 54 // encodes the pool size and a flag indicating if the guard is natural. It is 55 // possible to iterate through the code instructions skipping or examining the 56 // pools. E.g. it might be necessary to skip pools when search for, or patching, 57 // an instruction sequence. 58 // 59 // It is often required to keep a reference to a pool entry, to patch it after 60 // the buffer is finished. Each pool entry is assigned a unique index, counting 61 // up from zero (see the poolEntryCount slot below). These can be mapped back to 62 // the offset of the pool entry in the finished buffer, see poolEntryOffset(). 63 // 64 // The code supports no-pool regions, and for these the size of the region, in 65 // instructions, must be supplied. This size is used to determine if inserting 66 // the instructions would place a pool entry out of range, and if so then a pool 67 // is firstly flushed. The DEBUG code checks that the emitted code is within the 68 // supplied size to detect programming errors. See enterNoPool() and 69 // leaveNoPool(). 70 71 // The only planned instruction sets that require inline constant pools are the 72 // ARM, ARM64, and MIPS, and these all have fixed 32-bit sized instructions so 73 // for simplicity the code below is specialized for fixed 32-bit sized 74 // instructions and makes no attempt to support variable length 75 // instructions. The base assembler buffer which supports variable width 76 // instruction is used by the x86 and x64 backends. 77 78 // The AssemblerBufferWithConstantPools template class uses static callbacks to 79 // the provided Asm template argument class: 80 // 81 // void Asm::InsertIndexIntoTag(uint8_t* load_, uint32_t index) 82 // 83 // When allocEntry() is called to add a constant pool load with an associated 84 // constant pool entry, this callback is called to encode the index of the 85 // allocated constant pool entry into the load instruction. 86 // 87 // After the constant pool has been placed, PatchConstantPoolLoad() is called 88 // to update the load instruction with the right load offset. 89 // 90 // void Asm::WritePoolGuard(BufferOffset branch, 91 // Instruction* dest, 92 // BufferOffset afterPool) 93 // 94 // Write out the constant pool guard branch before emitting the pool. 95 // 96 // branch 97 // Offset of the guard branch in the buffer. 98 // 99 // dest 100 // Pointer into the buffer where the guard branch should be emitted. (Same 101 // as getInst(branch)). Space for guardSize_ instructions has been reserved. 102 // 103 // afterPool 104 // Offset of the first instruction after the constant pool. This includes 105 // both pool entries and branch veneers added after the pool data. 106 // 107 // void Asm::WritePoolHeader(uint8_t* start, Pool* p, bool isNatural) 108 // 109 // Write out the pool header which follows the guard branch. 110 // 111 // void Asm::PatchConstantPoolLoad(void* loadAddr, void* constPoolAddr) 112 // 113 // Re-encode a load of a constant pool entry after the location of the 114 // constant pool is known. 115 // 116 // The load instruction at loadAddr was previously passed to 117 // InsertIndexIntoTag(). The constPoolAddr is the final address of the 118 // constant pool in the assembler buffer. 119 // 120 // void Asm::PatchShortRangeBranchToVeneer(AssemblerBufferWithConstantPools*, 121 // unsigned rangeIdx, 122 // BufferOffset deadline, 123 // BufferOffset veneer) 124 // 125 // Patch a short-range branch to jump through a veneer before it goes out of 126 // range. 127 // 128 // rangeIdx, deadline 129 // These arguments were previously passed to registerBranchDeadline(). It is 130 // assumed that PatchShortRangeBranchToVeneer() knows how to compute the 131 // offset of the short-range branch from this information. 132 // 133 // veneer 134 // Space for a branch veneer, guaranteed to be <= deadline. At this 135 // position, guardSize_ * InstSize bytes are allocated. They should be 136 // initialized to the proper unconditional branch instruction. 137 // 138 // Unbound branches to the same unbound label are organized as a linked list: 139 // 140 // Label::offset -> Branch1 -> Branch2 -> Branch3 -> nil 141 // 142 // This callback should insert a new veneer branch into the list: 143 // 144 // Label::offset -> Branch1 -> Branch2 -> Veneer -> Branch3 -> nil 145 // 146 // When Assembler::bind() rewrites the branches with the real label offset, it 147 // probably has to bind Branch2 to target the veneer branch instead of jumping 148 // straight to the label. 149 150 namespace js { 151 namespace jit { 152 153 // BranchDeadlineSet - Keep track of pending branch deadlines. 154 // 155 // Some architectures like arm and arm64 have branch instructions with limited 156 // range. When assembling a forward branch, it is not always known if the final 157 // target label will be in range of the branch instruction. 158 // 159 // The BranchDeadlineSet data structure is used to keep track of the set of 160 // pending forward branches. It supports the following fast operations: 161 // 162 // 1. Get the earliest deadline in the set. 163 // 2. Add a new branch deadline. 164 // 3. Remove a branch deadline. 165 // 166 // Architectures may have different branch encodings with different ranges. Each 167 // supported range is assigned a small integer starting at 0. This data 168 // structure does not care about the actual range of branch instructions, just 169 // the latest buffer offset that can be reached - the deadline offset. 170 // 171 // Branched are stored as (rangeIdx, deadline) tuples. The target-specific code 172 // can compute the location of the branch itself from this information. This 173 // data structure does not need to know. 174 // 175 template <unsigned NumRanges> 176 class BranchDeadlineSet { 177 // Maintain a list of pending deadlines for each range separately. 178 // 179 // The offsets in each vector are always kept in ascending order. 180 // 181 // Because we have a separate vector for different ranges, as forward 182 // branches are added to the assembler buffer, their deadlines will 183 // always be appended to the vector corresponding to their range. 184 // 185 // When binding labels, we expect a more-or-less LIFO order of branch 186 // resolutions. This would always hold if we had strictly structured control 187 // flow. 188 // 189 // We allow branch deadlines to be added and removed in any order, but 190 // performance is best in the expected case of near LIFO order. 191 // 192 typedef Vector<BufferOffset, 8, LifoAllocPolicy<Fallible>> RangeVector; 193 194 // We really just want "RangeVector deadline_[NumRanges];", but each vector 195 // needs to be initialized with a LifoAlloc, and C++ doesn't bend that way. 196 // 197 // Use raw aligned storage instead and explicitly construct NumRanges 198 // vectors in our constructor. 199 mozilla::AlignedStorage2<RangeVector[NumRanges]> deadlineStorage_; 200 201 // Always access the range vectors through this method. vectorForRange(unsigned rangeIdx)202 RangeVector& vectorForRange(unsigned rangeIdx) { 203 MOZ_ASSERT(rangeIdx < NumRanges, "Invalid branch range index"); 204 return (*deadlineStorage_.addr())[rangeIdx]; 205 } 206 vectorForRange(unsigned rangeIdx)207 const RangeVector& vectorForRange(unsigned rangeIdx) const { 208 MOZ_ASSERT(rangeIdx < NumRanges, "Invalid branch range index"); 209 return (*deadlineStorage_.addr())[rangeIdx]; 210 } 211 212 // Maintain a precomputed earliest deadline at all times. 213 // This is unassigned only when all deadline vectors are empty. 214 BufferOffset earliest_; 215 216 // The range vector owning earliest_. Uninitialized when empty. 217 unsigned earliestRange_; 218 219 // Recompute the earliest deadline after it's been invalidated. recomputeEarliest()220 void recomputeEarliest() { 221 earliest_ = BufferOffset(); 222 for (unsigned r = 0; r < NumRanges; r++) { 223 auto& vec = vectorForRange(r); 224 if (!vec.empty() && (!earliest_.assigned() || vec[0] < earliest_)) { 225 earliest_ = vec[0]; 226 earliestRange_ = r; 227 } 228 } 229 } 230 231 // Update the earliest deadline if needed after inserting (rangeIdx, 232 // deadline). Always return true for convenience: 233 // return insert() && updateEarliest(). updateEarliest(unsigned rangeIdx,BufferOffset deadline)234 bool updateEarliest(unsigned rangeIdx, BufferOffset deadline) { 235 if (!earliest_.assigned() || deadline < earliest_) { 236 earliest_ = deadline; 237 earliestRange_ = rangeIdx; 238 } 239 return true; 240 } 241 242 public: BranchDeadlineSet(LifoAlloc & alloc)243 explicit BranchDeadlineSet(LifoAlloc& alloc) : earliestRange_(0) { 244 // Manually construct vectors in the uninitialized aligned storage. 245 // This is because C++ arrays can otherwise only be constructed with 246 // the default constructor. 247 for (unsigned r = 0; r < NumRanges; r++) { 248 new (&vectorForRange(r)) RangeVector(alloc); 249 } 250 } 251 ~BranchDeadlineSet()252 ~BranchDeadlineSet() { 253 // Aligned storage doesn't destruct its contents automatically. 254 for (unsigned r = 0; r < NumRanges; r++) { 255 vectorForRange(r).~RangeVector(); 256 } 257 } 258 259 // Is this set completely empty? empty()260 bool empty() const { return !earliest_.assigned(); } 261 262 // Get the total number of deadlines in the set. size()263 size_t size() const { 264 size_t count = 0; 265 for (unsigned r = 0; r < NumRanges; r++) { 266 count += vectorForRange(r).length(); 267 } 268 return count; 269 } 270 271 // Get the number of deadlines for the range with the most elements. maxRangeSize()272 size_t maxRangeSize() const { 273 size_t count = 0; 274 for (unsigned r = 0; r < NumRanges; r++) { 275 count = std::max(count, vectorForRange(r).length()); 276 } 277 return count; 278 } 279 280 // Get the first deadline that is still in the set. earliestDeadline()281 BufferOffset earliestDeadline() const { 282 MOZ_ASSERT(!empty()); 283 return earliest_; 284 } 285 286 // Get the range index corresponding to earliestDeadlineRange(). earliestDeadlineRange()287 unsigned earliestDeadlineRange() const { 288 MOZ_ASSERT(!empty()); 289 return earliestRange_; 290 } 291 292 // Add a (rangeIdx, deadline) tuple to the set. 293 // 294 // It is assumed that this tuple is not already in the set. 295 // This function performs best id the added deadline is later than any 296 // existing deadline for the same range index. 297 // 298 // Return true if the tuple was added, false if the tuple could not be added 299 // because of an OOM error. addDeadline(unsigned rangeIdx,BufferOffset deadline)300 bool addDeadline(unsigned rangeIdx, BufferOffset deadline) { 301 MOZ_ASSERT(deadline.assigned(), "Can only store assigned buffer offsets"); 302 // This is the vector where deadline should be saved. 303 auto& vec = vectorForRange(rangeIdx); 304 305 // Fast case: Simple append to the relevant array. This never affects 306 // the earliest deadline. 307 if (!vec.empty() && vec.back() < deadline) { 308 return vec.append(deadline); 309 } 310 311 // Fast case: First entry to the vector. We need to update earliest_. 312 if (vec.empty()) { 313 return vec.append(deadline) && updateEarliest(rangeIdx, deadline); 314 } 315 316 return addDeadlineSlow(rangeIdx, deadline); 317 } 318 319 private: 320 // General case of addDeadline. This is split into two functions such that 321 // the common case in addDeadline can be inlined while this part probably 322 // won't inline. addDeadlineSlow(unsigned rangeIdx,BufferOffset deadline)323 bool addDeadlineSlow(unsigned rangeIdx, BufferOffset deadline) { 324 auto& vec = vectorForRange(rangeIdx); 325 326 // Inserting into the middle of the vector. Use a log time binary search 327 // and a linear time insert(). 328 // Is it worthwhile special-casing the empty vector? 329 auto at = std::lower_bound(vec.begin(), vec.end(), deadline); 330 MOZ_ASSERT(at == vec.end() || *at != deadline, 331 "Cannot insert duplicate deadlines"); 332 return vec.insert(at, deadline) && updateEarliest(rangeIdx, deadline); 333 } 334 335 public: 336 // Remove a deadline from the set. 337 // If (rangeIdx, deadline) is not in the set, nothing happens. removeDeadline(unsigned rangeIdx,BufferOffset deadline)338 void removeDeadline(unsigned rangeIdx, BufferOffset deadline) { 339 auto& vec = vectorForRange(rangeIdx); 340 341 if (vec.empty()) { 342 return; 343 } 344 345 if (deadline == vec.back()) { 346 // Expected fast case: Structured control flow causes forward 347 // branches to be bound in reverse order. 348 vec.popBack(); 349 } else { 350 // Slow case: Binary search + linear erase. 351 auto where = std::lower_bound(vec.begin(), vec.end(), deadline); 352 if (where == vec.end() || *where != deadline) { 353 return; 354 } 355 vec.erase(where); 356 } 357 if (deadline == earliest_) { 358 recomputeEarliest(); 359 } 360 } 361 }; 362 363 // Specialization for architectures that don't need to track short-range 364 // branches. 365 template <> 366 class BranchDeadlineSet<0u> { 367 public: BranchDeadlineSet(LifoAlloc & alloc)368 explicit BranchDeadlineSet(LifoAlloc& alloc) {} empty()369 bool empty() const { return true; } size()370 size_t size() const { return 0; } maxRangeSize()371 size_t maxRangeSize() const { return 0; } earliestDeadline()372 BufferOffset earliestDeadline() const { MOZ_CRASH(); } earliestDeadlineRange()373 unsigned earliestDeadlineRange() const { MOZ_CRASH(); } addDeadline(unsigned rangeIdx,BufferOffset deadline)374 bool addDeadline(unsigned rangeIdx, BufferOffset deadline) { MOZ_CRASH(); } removeDeadline(unsigned rangeIdx,BufferOffset deadline)375 void removeDeadline(unsigned rangeIdx, BufferOffset deadline) { MOZ_CRASH(); } 376 }; 377 378 // The allocation unit size for pools. 379 typedef int32_t PoolAllocUnit; 380 381 // Hysteresis given to short-range branches. 382 // 383 // If any short-range branches will go out of range in the next N bytes, 384 // generate a veneer for them in the current pool. The hysteresis prevents the 385 // creation of many tiny constant pools for branch veneers. 386 const size_t ShortRangeBranchHysteresis = 128; 387 388 struct Pool { 389 private: 390 // The maximum program-counter relative offset below which the instruction 391 // set can encode. Different classes of intructions might support different 392 // ranges but for simplicity the minimum is used here, and for the ARM this 393 // is constrained to 1024 by the float load instructions. 394 const size_t maxOffset_; 395 // An offset to apply to program-counter relative offsets. The ARM has a 396 // bias of 8. 397 const unsigned bias_; 398 399 // The content of the pool entries. 400 Vector<PoolAllocUnit, 8, LifoAllocPolicy<Fallible>> poolData_; 401 402 // Flag that tracks OOM conditions. This is set after any append failed. 403 bool oom_; 404 405 // The limiting instruction and pool-entry pair. The instruction program 406 // counter relative offset of this limiting instruction will go out of range 407 // first as the pool position moves forward. It is more efficient to track 408 // just this limiting pair than to recheck all offsets when testing if the 409 // pool needs to be dumped. 410 // 411 // 1. The actual offset of the limiting instruction referencing the limiting 412 // pool entry. 413 BufferOffset limitingUser; 414 // 2. The pool entry index of the limiting pool entry. 415 unsigned limitingUsee; 416 417 public: 418 // A record of the code offset of instructions that reference pool 419 // entries. These instructions need to be patched when the actual position 420 // of the instructions and pools are known, and for the code below this 421 // occurs when each pool is finished, see finishPool(). 422 Vector<BufferOffset, 8, LifoAllocPolicy<Fallible>> loadOffsets; 423 424 // Create a Pool. Don't allocate anything from lifoAloc, just capture its 425 // reference. PoolPool426 explicit Pool(size_t maxOffset, unsigned bias, LifoAlloc& lifoAlloc) 427 : maxOffset_(maxOffset), 428 bias_(bias), 429 poolData_(lifoAlloc), 430 oom_(false), 431 limitingUser(), 432 limitingUsee(INT_MIN), 433 loadOffsets(lifoAlloc) {} 434 435 // If poolData() returns nullptr then oom_ will also be true. poolDataPool436 const PoolAllocUnit* poolData() const { return poolData_.begin(); } 437 numEntriesPool438 unsigned numEntries() const { return poolData_.length(); } 439 getPoolSizePool440 size_t getPoolSize() const { return numEntries() * sizeof(PoolAllocUnit); } 441 oomPool442 bool oom() const { return oom_; } 443 444 // Update the instruction/pool-entry pair that limits the position of the 445 // pool. The nextInst is the actual offset of the new instruction being 446 // allocated. 447 // 448 // This is comparing the offsets, see checkFull() below for the equation, 449 // but common expressions on both sides have been canceled from the ranges 450 // being compared. Notably, the poolOffset cancels out, so the limiting pair 451 // does not depend on where the pool is placed. updateLimiterPool452 void updateLimiter(BufferOffset nextInst) { 453 ptrdiff_t oldRange = 454 limitingUsee * sizeof(PoolAllocUnit) - limitingUser.getOffset(); 455 ptrdiff_t newRange = getPoolSize() - nextInst.getOffset(); 456 if (!limitingUser.assigned() || newRange > oldRange) { 457 // We have a new largest range! 458 limitingUser = nextInst; 459 limitingUsee = numEntries(); 460 } 461 } 462 463 // Check if inserting a pool at the actual offset poolOffset would place 464 // pool entries out of reach. This is called before inserting instructions 465 // to check that doing so would not push pool entries out of reach, and if 466 // so then the pool would need to be firstly dumped. The poolOffset is the 467 // first word of the pool, after the guard and header and alignment fill. checkFullPool468 bool checkFull(size_t poolOffset) const { 469 // Not full if there are no uses. 470 if (!limitingUser.assigned()) { 471 return false; 472 } 473 size_t offset = poolOffset + limitingUsee * sizeof(PoolAllocUnit) - 474 (limitingUser.getOffset() + bias_); 475 return offset >= maxOffset_; 476 } 477 478 static const unsigned OOM_FAIL = unsigned(-1); 479 insertEntryPool480 unsigned insertEntry(unsigned num, uint8_t* data, BufferOffset off, 481 LifoAlloc& lifoAlloc) { 482 if (oom_) { 483 return OOM_FAIL; 484 } 485 unsigned ret = numEntries(); 486 if (!poolData_.append((PoolAllocUnit*)data, num) || 487 !loadOffsets.append(off)) { 488 oom_ = true; 489 return OOM_FAIL; 490 } 491 return ret; 492 } 493 resetPool494 void reset() { 495 poolData_.clear(); 496 loadOffsets.clear(); 497 498 limitingUser = BufferOffset(); 499 limitingUsee = -1; 500 } 501 }; 502 503 // Template arguments: 504 // 505 // SliceSize 506 // Number of bytes in each allocated BufferSlice. See 507 // AssemblerBuffer::SliceSize. 508 // 509 // InstSize 510 // Size in bytes of the fixed-size instructions. This should be equal to 511 // sizeof(Inst). This is only needed here because the buffer is defined before 512 // the Instruction. 513 // 514 // Inst 515 // The actual type used to represent instructions. This is only really used as 516 // the return type of the getInst() method. 517 // 518 // Asm 519 // Class defining the needed static callback functions. See documentation of 520 // the Asm::* callbacks above. 521 // 522 // NumShortBranchRanges 523 // The number of short branch ranges to support. This can be 0 if no support 524 // for tracking short range branches is needed. The 525 // AssemblerBufferWithConstantPools class does not need to know what the range 526 // of branches is - it deals in branch 'deadlines' which is the last buffer 527 // position that a short-range forward branch can reach. It is assumed that 528 // the Asm class is able to find the actual branch instruction given a 529 // (range-index, deadline) pair. 530 // 531 // 532 template <size_t SliceSize, size_t InstSize, class Inst, class Asm, 533 unsigned NumShortBranchRanges = 0> 534 struct AssemblerBufferWithConstantPools 535 : public AssemblerBuffer<SliceSize, Inst> { 536 private: 537 // The PoolEntry index counter. Each PoolEntry is given a unique index, 538 // counting up from zero, and these can be mapped back to the actual pool 539 // entry offset after finishing the buffer, see poolEntryOffset(). 540 size_t poolEntryCount; 541 542 public: 543 class PoolEntry { 544 size_t index_; 545 546 public: PoolEntryAssemblerBufferWithConstantPools547 explicit PoolEntry(size_t index) : index_(index) {} 548 PoolEntryAssemblerBufferWithConstantPools549 PoolEntry() : index_(-1) {} 550 indexAssemblerBufferWithConstantPools551 size_t index() const { return index_; } 552 }; 553 554 private: 555 typedef AssemblerBuffer<SliceSize, Inst> Parent; 556 using typename Parent::Slice; 557 558 // The size of a pool guard, in instructions. A branch around the pool. 559 const unsigned guardSize_; 560 // The size of the header that is put at the beginning of a full pool, in 561 // instruction sized units. 562 const unsigned headerSize_; 563 564 // The maximum pc relative offset encoded in instructions that reference 565 // pool entries. This is generally set to the maximum offset that can be 566 // encoded by the instructions, but for testing can be lowered to affect the 567 // pool placement and frequency of pool placement. 568 const size_t poolMaxOffset_; 569 570 // The bias on pc relative addressing mode offsets, in units of bytes. The 571 // ARM has a bias of 8 bytes. 572 const unsigned pcBias_; 573 574 // The current working pool. Copied out as needed before resetting. 575 Pool pool_; 576 577 // The buffer should be aligned to this address. 578 const size_t instBufferAlign_; 579 580 struct PoolInfo { 581 // The index of the first entry in this pool. 582 // Pool entries are numbered uniquely across all pools, starting from 0. 583 unsigned firstEntryIndex; 584 585 // The location of this pool's first entry in the main assembler buffer. 586 // Note that the pool guard and header come before this offset which 587 // points directly at the data. 588 BufferOffset offset; 589 PoolInfoAssemblerBufferWithConstantPools::PoolInfo590 explicit PoolInfo(unsigned index, BufferOffset data) 591 : firstEntryIndex(index), offset(data) {} 592 }; 593 594 // Info for each pool that has already been dumped. This does not include 595 // any entries in pool_. 596 Vector<PoolInfo, 8, LifoAllocPolicy<Fallible>> poolInfo_; 597 598 // Set of short-range forward branches that have not yet been bound. 599 // We may need to insert veneers if the final label turns out to be out of 600 // range. 601 // 602 // This set stores (rangeIdx, deadline) pairs instead of the actual branch 603 // locations. 604 BranchDeadlineSet<NumShortBranchRanges> branchDeadlines_; 605 606 // When true dumping pools is inhibited. 607 bool canNotPlacePool_; 608 609 #ifdef DEBUG 610 // State for validating the 'maxInst' argument to enterNoPool(). 611 // The buffer offset when entering the no-pool region. 612 size_t canNotPlacePoolStartOffset_; 613 // The maximum number of word sized instructions declared for the no-pool 614 // region. 615 size_t canNotPlacePoolMaxInst_; 616 #endif 617 618 // Instruction to use for alignment fill. 619 const uint32_t alignFillInst_; 620 621 // Insert a number of NOP instructions between each requested instruction at 622 // all locations at which a pool can potentially spill. This is useful for 623 // checking that instruction locations are correctly referenced and/or 624 // followed. 625 const uint32_t nopFillInst_; 626 const unsigned nopFill_; 627 628 // For inhibiting the insertion of fill NOPs in the dynamic context in which 629 // they are being inserted. 630 bool inhibitNops_; 631 632 public: 633 // A unique id within each JitContext, to identify pools in the debug 634 // spew. Set by the MacroAssembler, see getNextAssemblerId(). 635 int id; 636 637 private: 638 // The buffer slices are in a double linked list. getHeadAssemblerBufferWithConstantPools639 Slice* getHead() const { return this->head; } getTailAssemblerBufferWithConstantPools640 Slice* getTail() const { return this->tail; } 641 642 public: 643 // Create an assembler buffer. 644 // Note that this constructor is not allowed to actually allocate memory from 645 // this->lifoAlloc_ because the MacroAssembler constructor has not yet created 646 // an AutoJitContextAlloc. 647 AssemblerBufferWithConstantPools(unsigned guardSize, unsigned headerSize, 648 size_t instBufferAlign, size_t poolMaxOffset, 649 unsigned pcBias, uint32_t alignFillInst, 650 uint32_t nopFillInst, unsigned nopFill = 0) 651 : poolEntryCount(0), 652 guardSize_(guardSize), 653 headerSize_(headerSize), 654 poolMaxOffset_(poolMaxOffset), 655 pcBias_(pcBias), 656 pool_(poolMaxOffset, pcBias, this->lifoAlloc_), 657 instBufferAlign_(instBufferAlign), 658 poolInfo_(this->lifoAlloc_), 659 branchDeadlines_(this->lifoAlloc_), 660 canNotPlacePool_(false), 661 #ifdef DEBUG 662 canNotPlacePoolStartOffset_(0), 663 canNotPlacePoolMaxInst_(0), 664 #endif 665 alignFillInst_(alignFillInst), 666 nopFillInst_(nopFillInst), 667 nopFill_(nopFill), 668 inhibitNops_(false), 669 id(-1) { 670 } 671 672 // We need to wait until an AutoJitContextAlloc is created by the 673 // MacroAssembler before allocating any space. initWithAllocatorAssemblerBufferWithConstantPools674 void initWithAllocator() { 675 // We hand out references to lifoAlloc_ in the constructor. 676 // Check that no allocations were made then. 677 MOZ_ASSERT(this->lifoAlloc_.isEmpty(), 678 "Illegal LIFO allocations before AutoJitContextAlloc"); 679 } 680 681 private: sizeExcludingCurrentPoolAssemblerBufferWithConstantPools682 size_t sizeExcludingCurrentPool() const { 683 // Return the actual size of the buffer, excluding the current pending 684 // pool. 685 return this->nextOffset().getOffset(); 686 } 687 688 public: sizeAssemblerBufferWithConstantPools689 size_t size() const { 690 // Return the current actual size of the buffer. This is only accurate 691 // if there are no pending pool entries to dump, check. 692 MOZ_ASSERT_IF(!this->oom(), pool_.numEntries() == 0); 693 return sizeExcludingCurrentPool(); 694 } 695 696 private: insertNopFillAssemblerBufferWithConstantPools697 void insertNopFill() { 698 // Insert fill for testing. 699 if (nopFill_ > 0 && !inhibitNops_ && !canNotPlacePool_) { 700 inhibitNops_ = true; 701 702 // Fill using a branch-nop rather than a NOP so this can be 703 // distinguished and skipped. 704 for (size_t i = 0; i < nopFill_; i++) { 705 putInt(nopFillInst_); 706 } 707 708 inhibitNops_ = false; 709 } 710 } 711 712 static const unsigned OOM_FAIL = unsigned(-1); 713 static const unsigned DUMMY_INDEX = unsigned(-2); 714 715 // Check if it is possible to add numInst instructions and numPoolEntries 716 // constant pool entries without needing to flush the current pool. hasSpaceForInstsAssemblerBufferWithConstantPools717 bool hasSpaceForInsts(unsigned numInsts, unsigned numPoolEntries) const { 718 size_t nextOffset = sizeExcludingCurrentPool(); 719 // Earliest starting offset for the current pool after adding numInsts. 720 // This is the beginning of the pool entries proper, after inserting a 721 // guard branch + pool header. 722 size_t poolOffset = 723 nextOffset + (numInsts + guardSize_ + headerSize_) * InstSize; 724 725 // Any constant pool loads that would go out of range? 726 if (pool_.checkFull(poolOffset)) { 727 return false; 728 } 729 730 // Any short-range branch that would go out of range? 731 if (!branchDeadlines_.empty()) { 732 size_t deadline = branchDeadlines_.earliestDeadline().getOffset(); 733 size_t poolEnd = poolOffset + pool_.getPoolSize() + 734 numPoolEntries * sizeof(PoolAllocUnit); 735 736 // When NumShortBranchRanges > 1, is is possible for branch deadlines to 737 // expire faster than we can insert veneers. Suppose branches are 4 bytes 738 // each, we could have the following deadline set: 739 // 740 // Range 0: 40, 44, 48 741 // Range 1: 44, 48 742 // 743 // It is not good enough to start inserting veneers at the 40 deadline; we 744 // would not be able to create veneers for the second 44 deadline. 745 // Instead, we need to start at 32: 746 // 747 // 32: veneer(40) 748 // 36: veneer(44) 749 // 40: veneer(44) 750 // 44: veneer(48) 751 // 48: veneer(48) 752 // 753 // This is a pretty conservative solution to the problem: If we begin at 754 // the earliest deadline, we can always emit all veneers for the range 755 // that currently has the most pending deadlines. That may not leave room 756 // for veneers for the remaining ranges, so reserve space for those 757 // secondary range veneers assuming the worst case deadlines. 758 759 // Total pending secondary range veneer size. 760 size_t secondaryVeneers = guardSize_ * (branchDeadlines_.size() - 761 branchDeadlines_.maxRangeSize()); 762 763 if (deadline < poolEnd + secondaryVeneers) { 764 return false; 765 } 766 } 767 768 return true; 769 } 770 insertEntryForwardsAssemblerBufferWithConstantPools771 unsigned insertEntryForwards(unsigned numInst, unsigned numPoolEntries, 772 uint8_t* inst, uint8_t* data) { 773 // If inserting pool entries then find a new limiter before we do the 774 // range check. 775 if (numPoolEntries) { 776 pool_.updateLimiter(BufferOffset(sizeExcludingCurrentPool())); 777 } 778 779 if (!hasSpaceForInsts(numInst, numPoolEntries)) { 780 if (numPoolEntries) { 781 JitSpew(JitSpew_Pools, "[%d] Inserting pool entry caused a spill", id); 782 } else { 783 JitSpew(JitSpew_Pools, "[%d] Inserting instruction(%zu) caused a spill", 784 id, sizeExcludingCurrentPool()); 785 } 786 787 finishPool(numInst * InstSize); 788 if (this->oom()) { 789 return OOM_FAIL; 790 } 791 return insertEntryForwards(numInst, numPoolEntries, inst, data); 792 } 793 if (numPoolEntries) { 794 unsigned result = pool_.insertEntry(numPoolEntries, data, 795 this->nextOffset(), this->lifoAlloc_); 796 if (result == Pool::OOM_FAIL) { 797 this->fail_oom(); 798 return OOM_FAIL; 799 } 800 return result; 801 } 802 803 // The pool entry index is returned above when allocating an entry, but 804 // when not allocating an entry a dummy value is returned - it is not 805 // expected to be used by the caller. 806 return DUMMY_INDEX; 807 } 808 809 public: 810 // Get the next buffer offset where an instruction would be inserted. 811 // This may flush the current constant pool before returning nextOffset(). nextInstrOffsetAssemblerBufferWithConstantPools812 BufferOffset nextInstrOffset() { 813 if (!hasSpaceForInsts(/* numInsts= */ 1, /* numPoolEntries= */ 0)) { 814 JitSpew(JitSpew_Pools, 815 "[%d] nextInstrOffset @ %d caused a constant pool spill", id, 816 this->nextOffset().getOffset()); 817 finishPool(ShortRangeBranchHysteresis); 818 } 819 return this->nextOffset(); 820 } 821 822 MOZ_NEVER_INLINE 823 BufferOffset allocEntry(size_t numInst, unsigned numPoolEntries, 824 uint8_t* inst, uint8_t* data, 825 PoolEntry* pe = nullptr) { 826 // The allocation of pool entries is not supported in a no-pool region, 827 // check. 828 MOZ_ASSERT_IF(numPoolEntries, !canNotPlacePool_); 829 830 if (this->oom()) { 831 return BufferOffset(); 832 } 833 834 insertNopFill(); 835 836 #ifdef JS_JITSPEW 837 if (numPoolEntries && JitSpewEnabled(JitSpew_Pools)) { 838 JitSpew(JitSpew_Pools, "[%d] Inserting %d entries into pool", id, 839 numPoolEntries); 840 JitSpewStart(JitSpew_Pools, "[%d] data is: 0x", id); 841 size_t length = numPoolEntries * sizeof(PoolAllocUnit); 842 for (unsigned idx = 0; idx < length; idx++) { 843 JitSpewCont(JitSpew_Pools, "%02x", data[length - idx - 1]); 844 if (((idx & 3) == 3) && (idx + 1 != length)) { 845 JitSpewCont(JitSpew_Pools, "_"); 846 } 847 } 848 JitSpewFin(JitSpew_Pools); 849 } 850 #endif 851 852 // Insert the pool value. 853 unsigned index = insertEntryForwards(numInst, numPoolEntries, inst, data); 854 if (this->oom()) { 855 return BufferOffset(); 856 } 857 858 // Now to get an instruction to write. 859 PoolEntry retPE; 860 if (numPoolEntries) { 861 JitSpew(JitSpew_Pools, "[%d] Entry has index %u, offset %zu", id, index, 862 sizeExcludingCurrentPool()); 863 Asm::InsertIndexIntoTag(inst, index); 864 // Figure out the offset within the pool entries. 865 retPE = PoolEntry(poolEntryCount); 866 poolEntryCount += numPoolEntries; 867 } 868 // Now inst is a valid thing to insert into the instruction stream. 869 if (pe != nullptr) { 870 *pe = retPE; 871 } 872 return this->putBytes(numInst * InstSize, inst); 873 } 874 875 // putInt is the workhorse for the assembler and higher-level buffer 876 // abstractions: it places one instruction into the instruction stream. 877 // Under normal circumstances putInt should just check that the constant 878 // pool does not need to be flushed, that there is space for the single word 879 // of the instruction, and write that word and update the buffer pointer. 880 // 881 // To do better here we need a status variable that handles both nopFill_ 882 // and capacity, so that we can quickly know whether to go the slow path. 883 // That could be a variable that has the remaining number of simple 884 // instructions that can be inserted before a more expensive check, 885 // which is set to zero when nopFill_ is set. 886 // 887 // We assume that we don't have to check this->oom() if there is space to 888 // insert a plain instruction; there will always come a later time when it 889 // will be checked anyway. 890 891 MOZ_ALWAYS_INLINE putIntAssemblerBufferWithConstantPools892 BufferOffset putInt(uint32_t value) { 893 if (nopFill_ || 894 !hasSpaceForInsts(/* numInsts= */ 1, /* numPoolEntries= */ 0)) { 895 return allocEntry(1, 0, (uint8_t*)&value, nullptr, nullptr); 896 } 897 898 #if defined(JS_CODEGEN_ARM) || defined(JS_CODEGEN_ARM64) || \ 899 defined(JS_CODEGEN_MIPS32) || defined(JS_CODEGEN_MIPS64) 900 return this->putU32Aligned(value); 901 #else 902 return this->AssemblerBuffer<SliceSize, Inst>::putInt(value); 903 #endif 904 } 905 906 // Register a short-range branch deadline. 907 // 908 // After inserting a short-range forward branch, call this method to 909 // register the branch 'deadline' which is the last buffer offset that the 910 // branch instruction can reach. 911 // 912 // When the branch is bound to a destination label, call 913 // unregisterBranchDeadline() to stop tracking this branch, 914 // 915 // If the assembled code is about to exceed the registered branch deadline, 916 // and unregisterBranchDeadline() has not yet been called, an 917 // instruction-sized constant pool entry is allocated before the branch 918 // deadline. 919 // 920 // rangeIdx 921 // A number < NumShortBranchRanges identifying the range of the branch. 922 // 923 // deadline 924 // The highest buffer offset the the short-range branch can reach 925 // directly. 926 // registerBranchDeadlineAssemblerBufferWithConstantPools927 void registerBranchDeadline(unsigned rangeIdx, BufferOffset deadline) { 928 if (!this->oom() && !branchDeadlines_.addDeadline(rangeIdx, deadline)) { 929 this->fail_oom(); 930 } 931 } 932 933 // Un-register a short-range branch deadline. 934 // 935 // When a short-range branch has been successfully bound to its destination 936 // label, call this function to stop traching the branch. 937 // 938 // The (rangeIdx, deadline) pair must be previously registered. 939 // unregisterBranchDeadlineAssemblerBufferWithConstantPools940 void unregisterBranchDeadline(unsigned rangeIdx, BufferOffset deadline) { 941 if (!this->oom()) { 942 branchDeadlines_.removeDeadline(rangeIdx, deadline); 943 } 944 } 945 946 private: 947 // Are any short-range branches about to expire? hasExpirableShortRangeBranchesAssemblerBufferWithConstantPools948 bool hasExpirableShortRangeBranches(size_t reservedBytes) const { 949 if (branchDeadlines_.empty()) { 950 return false; 951 } 952 953 // Include branches that would expire in the next N bytes. The reservedBytes 954 // argument avoids the needless creation of many tiny constant pools. 955 // 956 // As the reservedBytes could be of any sizes such as SIZE_MAX, in the case 957 // of flushPool, we have to check for overflow when comparing the deadline 958 // with our expected reserved bytes. 959 size_t deadline = branchDeadlines_.earliestDeadline().getOffset(); 960 using CheckedSize = mozilla::CheckedInt<size_t>; 961 CheckedSize current(this->nextOffset().getOffset()); 962 CheckedSize poolFreeSpace(reservedBytes); 963 auto future = current + poolFreeSpace; 964 return !future.isValid() || deadline < future.value(); 965 } 966 isPoolEmptyForAssemblerBufferWithConstantPools967 bool isPoolEmptyFor(size_t bytes) const { 968 return pool_.numEntries() == 0 && !hasExpirableShortRangeBranches(bytes); 969 } finishPoolAssemblerBufferWithConstantPools970 void finishPool(size_t reservedBytes) { 971 JitSpew(JitSpew_Pools, 972 "[%d] Attempting to finish pool %zu with %u entries.", id, 973 poolInfo_.length(), pool_.numEntries()); 974 975 if (reservedBytes < ShortRangeBranchHysteresis) { 976 reservedBytes = ShortRangeBranchHysteresis; 977 } 978 979 if (isPoolEmptyFor(reservedBytes)) { 980 // If there is no data in the pool being dumped, don't dump anything. 981 JitSpew(JitSpew_Pools, "[%d] Aborting because the pool is empty", id); 982 return; 983 } 984 985 // Should not be placing a pool in a no-pool region, check. 986 MOZ_ASSERT(!canNotPlacePool_); 987 988 // Dump the pool with a guard branch around the pool. 989 BufferOffset guard = this->putBytes(guardSize_ * InstSize, nullptr); 990 BufferOffset header = this->putBytes(headerSize_ * InstSize, nullptr); 991 BufferOffset data = this->putBytesLarge(pool_.getPoolSize(), 992 (const uint8_t*)pool_.poolData()); 993 if (this->oom()) { 994 return; 995 } 996 997 // Now generate branch veneers for any short-range branches that are 998 // about to expire. 999 while (hasExpirableShortRangeBranches(reservedBytes)) { 1000 unsigned rangeIdx = branchDeadlines_.earliestDeadlineRange(); 1001 BufferOffset deadline = branchDeadlines_.earliestDeadline(); 1002 1003 // Stop tracking this branch. The Asm callback below may register 1004 // new branches to track. 1005 branchDeadlines_.removeDeadline(rangeIdx, deadline); 1006 1007 // Make room for the veneer. Same as a pool guard branch. 1008 BufferOffset veneer = this->putBytes(guardSize_ * InstSize, nullptr); 1009 if (this->oom()) { 1010 return; 1011 } 1012 1013 // Fix the branch so it targets the veneer. 1014 // The Asm class knows how to find the original branch given the 1015 // (rangeIdx, deadline) pair. 1016 Asm::PatchShortRangeBranchToVeneer(this, rangeIdx, deadline, veneer); 1017 } 1018 1019 // We only reserved space for the guard branch and pool header. 1020 // Fill them in. 1021 BufferOffset afterPool = this->nextOffset(); 1022 Asm::WritePoolGuard(guard, this->getInst(guard), afterPool); 1023 Asm::WritePoolHeader((uint8_t*)this->getInst(header), &pool_, false); 1024 1025 // With the pool's final position determined it is now possible to patch 1026 // the instructions that reference entries in this pool, and this is 1027 // done incrementally as each pool is finished. 1028 size_t poolOffset = data.getOffset(); 1029 1030 unsigned idx = 0; 1031 for (BufferOffset* iter = pool_.loadOffsets.begin(); 1032 iter != pool_.loadOffsets.end(); ++iter, ++idx) { 1033 // All entries should be before the pool. 1034 MOZ_ASSERT(iter->getOffset() < guard.getOffset()); 1035 1036 // Everything here is known so we can safely do the necessary 1037 // substitutions. 1038 Inst* inst = this->getInst(*iter); 1039 size_t codeOffset = poolOffset - iter->getOffset(); 1040 1041 // That is, PatchConstantPoolLoad wants to be handed the address of 1042 // the pool entry that is being loaded. We need to do a non-trivial 1043 // amount of math here, since the pool that we've made does not 1044 // actually reside there in memory. 1045 JitSpew(JitSpew_Pools, "[%d] Fixing entry %d offset to %zu", id, idx, 1046 codeOffset); 1047 Asm::PatchConstantPoolLoad(inst, (uint8_t*)inst + codeOffset); 1048 } 1049 1050 // Record the pool info. 1051 unsigned firstEntry = poolEntryCount - pool_.numEntries(); 1052 if (!poolInfo_.append(PoolInfo(firstEntry, data))) { 1053 this->fail_oom(); 1054 return; 1055 } 1056 1057 // Reset everything to the state that it was in when we started. 1058 pool_.reset(); 1059 } 1060 1061 public: flushPoolAssemblerBufferWithConstantPools1062 void flushPool() { 1063 if (this->oom()) { 1064 return; 1065 } 1066 JitSpew(JitSpew_Pools, "[%d] Requesting a pool flush", id); 1067 finishPool(SIZE_MAX); 1068 } 1069 enterNoPoolAssemblerBufferWithConstantPools1070 void enterNoPool(size_t maxInst) { 1071 if (this->oom()) { 1072 return; 1073 } 1074 // Don't allow re-entry. 1075 MOZ_ASSERT(!canNotPlacePool_); 1076 insertNopFill(); 1077 1078 // Check if the pool will spill by adding maxInst instructions, and if 1079 // so then finish the pool before entering the no-pool region. It is 1080 // assumed that no pool entries are allocated in a no-pool region and 1081 // this is asserted when allocating entries. 1082 if (!hasSpaceForInsts(maxInst, 0)) { 1083 JitSpew(JitSpew_Pools, "[%d] No-Pool instruction(%zu) caused a spill.", 1084 id, sizeExcludingCurrentPool()); 1085 finishPool(maxInst * InstSize); 1086 MOZ_ASSERT(hasSpaceForInsts(maxInst, 0)); 1087 } 1088 1089 #ifdef DEBUG 1090 // Record the buffer position to allow validating maxInst when leaving 1091 // the region. 1092 canNotPlacePoolStartOffset_ = this->nextOffset().getOffset(); 1093 canNotPlacePoolMaxInst_ = maxInst; 1094 #endif 1095 1096 canNotPlacePool_ = true; 1097 } 1098 leaveNoPoolAssemblerBufferWithConstantPools1099 void leaveNoPool() { 1100 if (this->oom()) { 1101 canNotPlacePool_ = false; 1102 return; 1103 } 1104 MOZ_ASSERT(canNotPlacePool_); 1105 canNotPlacePool_ = false; 1106 1107 // Validate the maxInst argument supplied to enterNoPool(). 1108 MOZ_ASSERT(this->nextOffset().getOffset() - canNotPlacePoolStartOffset_ <= 1109 canNotPlacePoolMaxInst_ * InstSize); 1110 } 1111 enterNoNopsAssemblerBufferWithConstantPools1112 void enterNoNops() { 1113 MOZ_ASSERT(!inhibitNops_); 1114 inhibitNops_ = true; 1115 } leaveNoNopsAssemblerBufferWithConstantPools1116 void leaveNoNops() { 1117 MOZ_ASSERT(inhibitNops_); 1118 inhibitNops_ = false; 1119 } assertNoPoolAndNoNopsAssemblerBufferWithConstantPools1120 void assertNoPoolAndNoNops() { 1121 MOZ_ASSERT(inhibitNops_); 1122 MOZ_ASSERT_IF(!this->oom(), isPoolEmptyFor(InstSize) || canNotPlacePool_); 1123 } 1124 alignAssemblerBufferWithConstantPools1125 void align(unsigned alignment) { align(alignment, alignFillInst_); } 1126 alignAssemblerBufferWithConstantPools1127 void align(unsigned alignment, uint32_t pattern) { 1128 MOZ_ASSERT(mozilla::IsPowerOfTwo(alignment)); 1129 MOZ_ASSERT(alignment >= InstSize); 1130 1131 // A pool many need to be dumped at this point, so insert NOP fill here. 1132 insertNopFill(); 1133 1134 // Check if the code position can be aligned without dumping a pool. 1135 unsigned requiredFill = sizeExcludingCurrentPool() & (alignment - 1); 1136 if (requiredFill == 0) { 1137 return; 1138 } 1139 requiredFill = alignment - requiredFill; 1140 1141 // Add an InstSize because it is probably not useful for a pool to be 1142 // dumped at the aligned code position. 1143 if (!hasSpaceForInsts(requiredFill / InstSize + 1, 0)) { 1144 // Alignment would cause a pool dump, so dump the pool now. 1145 JitSpew(JitSpew_Pools, "[%d] Alignment of %d at %zu caused a spill.", id, 1146 alignment, sizeExcludingCurrentPool()); 1147 finishPool(requiredFill); 1148 } 1149 1150 bool prevInhibitNops = inhibitNops_; 1151 inhibitNops_ = true; 1152 while ((sizeExcludingCurrentPool() & (alignment - 1)) && !this->oom()) { 1153 putInt(pattern); 1154 } 1155 inhibitNops_ = prevInhibitNops; 1156 } 1157 1158 public: executableCopyAssemblerBufferWithConstantPools1159 void executableCopy(uint8_t* dest) { 1160 if (this->oom()) { 1161 return; 1162 } 1163 // The pools should have all been flushed, check. 1164 MOZ_ASSERT(pool_.numEntries() == 0); 1165 for (Slice* cur = getHead(); cur != nullptr; cur = cur->getNext()) { 1166 memcpy(dest, &cur->instructions[0], cur->length()); 1167 dest += cur->length(); 1168 } 1169 } 1170 appendRawCodeAssemblerBufferWithConstantPools1171 bool appendRawCode(const uint8_t* code, size_t numBytes) { 1172 if (this->oom()) { 1173 return false; 1174 } 1175 // The pools should have all been flushed, check. 1176 MOZ_ASSERT(pool_.numEntries() == 0); 1177 while (numBytes > SliceSize) { 1178 this->putBytes(SliceSize, code); 1179 numBytes -= SliceSize; 1180 code += SliceSize; 1181 } 1182 this->putBytes(numBytes, code); 1183 return !this->oom(); 1184 } 1185 1186 public: poolEntryOffsetAssemblerBufferWithConstantPools1187 size_t poolEntryOffset(PoolEntry pe) const { 1188 MOZ_ASSERT(pe.index() < poolEntryCount - pool_.numEntries(), 1189 "Invalid pool entry, or not flushed yet."); 1190 // Find the pool containing pe.index(). 1191 // The array is sorted, so we can use a binary search. 1192 auto b = poolInfo_.begin(), e = poolInfo_.end(); 1193 // A note on asymmetric types in the upper_bound comparator: 1194 // http://permalink.gmane.org/gmane.comp.compilers.clang.devel/10101 1195 auto i = std::upper_bound(b, e, pe.index(), 1196 [](size_t value, const PoolInfo& entry) { 1197 return value < entry.firstEntryIndex; 1198 }); 1199 // Since upper_bound finds the first pool greater than pe, 1200 // we want the previous one which is the last one less than or equal. 1201 MOZ_ASSERT(i != b, "PoolInfo not sorted or empty?"); 1202 --i; 1203 // The i iterator now points to the pool containing pe.index. 1204 MOZ_ASSERT(i->firstEntryIndex <= pe.index() && 1205 (i + 1 == e || (i + 1)->firstEntryIndex > pe.index())); 1206 // Compute the byte offset into the pool. 1207 unsigned relativeIndex = pe.index() - i->firstEntryIndex; 1208 return i->offset.getOffset() + relativeIndex * sizeof(PoolAllocUnit); 1209 } 1210 }; 1211 1212 } // namespace jit 1213 } // namespace js 1214 1215 #endif // jit_shared_IonAssemblerBufferWithConstantPools_h 1216