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
26using namespace glow;
27using 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//
38const 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.
51void 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