1 | /** |
2 | * Copyright (c) Glow Contributors. See CONTRIBUTORS file. |
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 | // The online list ordering algorithm is based on Bender et al., "Two Simplified |
18 | // Algorithms for Maintaining Order in a List." |
19 | |
20 | #include "glow/Base/TaggedList.h" |
21 | #include "llvm/Support/MathExtras.h" |
22 | |
23 | #include <algorithm> |
24 | #include <cassert> |
25 | |
26 | using namespace glow; |
27 | using namespace tagged_list_details; |
28 | |
29 | // Fixed-point (0.32) factors for computing density limits at each tree level. |
30 | // The table is indexed by "size class" which is floor(log2(size)). |
31 | // |
32 | // Computed by this Python code: |
33 | // |
34 | // for s in range(31): |
35 | // f = 2 ** (s/31.0 - 1) |
36 | // print(hex(int(f * 2**32)) + ',') |
37 | // |
38 | const uint32_t factorForSizeClass[32] = { |
39 | 0x80000000, 0x82e4ee78, 0x85da9dd7, 0x88e16f18, 0x8bf9c566, 0x8f24062b, |
40 | 0x9260991c, 0x95afe846, 0x9912601d, 0x9c886f86, 0xa01287ec, 0xa3b11d46, |
41 | 0xa764a62f, 0xab2d9bec, 0xaf0c7a83, 0xb301c0c6, 0xb70df068, 0xbb318e08, |
42 | 0xbf6d2145, 0xc3c134d0, 0xc82e567d, 0xccb51753, 0xd1560ba3, 0xd611cb16, |
43 | 0xdae8f0c7, 0xdfdc1b4d, 0xe4ebecdb, 0xea190b4a, 0xef642035, 0xf4cdd90f, |
44 | 0xfa56e732, 0xffffffff}; |
45 | |
46 | // Given two adjacent instruction with the same tag, renumber instructions |
47 | // such that the entire list is strictly increasing. |
48 | // |
49 | // It is assumed that the sub-list up to and including lo is monotonic, and so |
50 | // is the sub-list starting at hi. |
51 | void ListImpl::renumber(NodeBase *lo, NodeBase *hi) { |
52 | assert(hi != &sentinel_); |
53 | assert(lo->nodeTag_ == hi->nodeTag_); |
54 | assert(lo->nextTaggedNode_ == hi); |
55 | |
56 | uint32_t count = 2; // maintained as count(lo..hi). |
57 | NodeBase *insertionPoint = hi; |
58 | |
59 | // Start at tree level 0 which is the leaves. |
60 | unsigned level = 0; |
61 | // Inclusive tag range below the current tree node. |
62 | uint32_t tagFloor = lo->nodeTag_; |
63 | uint32_t tagCeil = lo->nodeTag_; |
64 | // Maximum number of nodes at this level. |
65 | uint32_t limit = 1; |
66 | |
67 | // 1.31 fixed-point factor to get the next level limit. |
68 | unsigned sizeClass = llvm::Log2_32(size_); |
69 | uint32_t factor = factorForSizeClass[sizeClass]; |
70 | |
71 | // Increase the tree level until we're inside the limit. |
72 | while (level < 32 && limit < count) { |
73 | // Half the size of the next level; |
74 | uint32_t half = UINT32_C(1) << level; |
75 | |
76 | // Advance level and limit. |
77 | level++; |
78 | limit = (uint64_t(2 * limit) * factor) >> 32; |
79 | // Always round up. This is important at the very low levels. |
80 | limit++; |
81 | |
82 | // The window doubles by moving either the floor or the ceiling. |
83 | if (tagFloor & half) { |
84 | // Move the floor down; |
85 | tagFloor -= half; |
86 | while (lo != &sentinel_ && lo->prevTaggedNode_->nodeTag_ >= tagFloor) { |
87 | lo = lo->prevTaggedNode_; |
88 | count++; |
89 | } |
90 | } else { |
91 | // Move the ceiling up. |
92 | tagCeil += half; |
93 | while (hi->nextTaggedNode_ != &sentinel_ && |
94 | hi->nextTaggedNode_->nodeTag_ <= tagCeil) { |
95 | hi = hi->nextTaggedNode_; |
96 | count++; |
97 | } |
98 | } |
99 | } |
100 | |
101 | // The window is now wide enough, so we can assign tags from the inclusive |
102 | // range tagFloor..tagCeil to the instructions in the inclusive range |
103 | // lo..hi. |
104 | uint32_t dy = tagCeil - tagFloor; |
105 | uint32_t dx = count - 1; |
106 | |
107 | // Make an even larger hold at the insertion point than is strictly |
108 | // necessary. This anticipates future insertions near the same point. |
109 | dx += std::min(dx / 8, dy - dx); |
110 | uint32_t step = dy / dx; |
111 | |
112 | for (; lo != insertionPoint; lo = lo->nextTaggedNode_, tagFloor += step) { |
113 | lo->nodeTag_ = tagFloor; |
114 | } |
115 | for (; hi != insertionPoint; hi = hi->prevTaggedNode_, tagCeil -= step) { |
116 | hi->nodeTag_ = tagCeil; |
117 | } |
118 | hi->nodeTag_ = tagCeil; |
119 | } |
120 | |