1 // Copyright 2020 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/codegen/aligned-slot-allocator.h"
6
7 #include "src/base/bits.h"
8 #include "src/base/logging.h"
9
10 namespace v8 {
11 namespace internal {
12
NextSlot(int n) const13 int AlignedSlotAllocator::NextSlot(int n) const {
14 DCHECK(n == 1 || n == 2 || n == 4);
15 if (n <= 1 && IsValid(next1_)) return next1_;
16 if (n <= 2 && IsValid(next2_)) return next2_;
17 DCHECK(IsValid(next4_));
18 return next4_;
19 }
20
Allocate(int n)21 int AlignedSlotAllocator::Allocate(int n) {
22 DCHECK(n == 1 || n == 2 || n == 4);
23 // Check invariants.
24 DCHECK_EQ(0, next4_ & 3);
25 DCHECK_IMPLIES(IsValid(next2_), (next2_ & 1) == 0);
26
27 // The sentinel value kInvalidSlot is used to indicate no slot.
28 // next1_ is the index of the 1 slot fragment, or kInvalidSlot.
29 // next2_ is the 2-aligned index of the 2 slot fragment, or kInvalidSlot.
30 // next4_ is the 4-aligned index of the next 4 slot group. It is always valid.
31 // In order to ensure we only have a single 1- or 2-slot fragment, we greedily
32 // use any fragment that satisfies the request.
33 int result = kInvalidSlot;
34 switch (n) {
35 case 1: {
36 if (IsValid(next1_)) {
37 result = next1_;
38 next1_ = kInvalidSlot;
39 } else if (IsValid(next2_)) {
40 result = next2_;
41 next1_ = result + 1;
42 next2_ = kInvalidSlot;
43 } else {
44 result = next4_;
45 next1_ = result + 1;
46 next2_ = result + 2;
47 next4_ += 4;
48 }
49 break;
50 }
51 case 2: {
52 if (IsValid(next2_)) {
53 result = next2_;
54 next2_ = kInvalidSlot;
55 } else {
56 result = next4_;
57 next2_ = result + 2;
58 next4_ += 4;
59 }
60 break;
61 }
62 case 4: {
63 result = next4_;
64 next4_ += 4;
65 break;
66 }
67 default:
68 UNREACHABLE();
69 }
70 DCHECK(IsValid(result));
71 size_ = std::max(size_, result + n);
72 return result;
73 }
74
AllocateUnaligned(int n)75 int AlignedSlotAllocator::AllocateUnaligned(int n) {
76 DCHECK_GE(n, 0);
77 // Check invariants.
78 DCHECK_EQ(0, next4_ & 3);
79 DCHECK_IMPLIES(IsValid(next2_), (next2_ & 1) == 0);
80
81 // Reserve |n| slots at |size_|, invalidate fragments below the new |size_|,
82 // and add any new fragments beyond the new |size_|.
83 int result = size_;
84 size_ += n;
85 switch (size_ & 3) {
86 case 0: {
87 next1_ = next2_ = kInvalidSlot;
88 next4_ = size_;
89 break;
90 }
91 case 1: {
92 next1_ = size_;
93 next2_ = size_ + 1;
94 next4_ = size_ + 3;
95 break;
96 }
97 case 2: {
98 next1_ = kInvalidSlot;
99 next2_ = size_;
100 next4_ = size_ + 2;
101 break;
102 }
103 case 3: {
104 next1_ = size_;
105 next2_ = kInvalidSlot;
106 next4_ = size_ + 1;
107 break;
108 }
109 }
110 return result;
111 }
112
Align(int n)113 int AlignedSlotAllocator::Align(int n) {
114 DCHECK(base::bits::IsPowerOfTwo(n));
115 DCHECK_LE(n, 4);
116 int mask = n - 1;
117 int misalignment = size_ & mask;
118 int padding = (n - misalignment) & mask;
119 AllocateUnaligned(padding);
120 return padding;
121 }
122
123 } // namespace internal
124 } // namespace v8
125