1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
// SPDX-License-Identifier: GPL-3.0-or-later
#include "RISCVImmediateMaterialization.h"
#include <algorithm>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
namespace rcc::riscv {
namespace {
[[nodiscard]] constexpr bool fitsSigned(std::int64_t Value, std::uint32_t Bits) noexcept {
const std::int64_t Minimum = -(std::int64_t{1} << (Bits - 1U));
const std::int64_t Maximum = (std::int64_t{1} << (Bits - 1U)) - 1;
return Value >= Minimum && Value <= Maximum;
}
[[nodiscard]] constexpr std::int64_t signExtend(std::uint64_t Value, std::uint32_t Bits) noexcept {
const std::uint64_t Mask = (std::uint64_t{1} << Bits) - 1U;
const std::uint64_t Sign = std::uint64_t{1} << (Bits - 1U);
Value &= Mask;
if ((Value & Sign) != 0)
Value |= ~Mask;
return std::bit_cast<std::int64_t>(Value);
}
[[nodiscard]] std::size_t baseBuildCost(std::int64_t Value) noexcept {
const std::uint64_t Bits = static_cast<std::uint64_t>(Value);
if (fitsSigned(Value, 32)) {
const std::uint64_t High20 = ((Bits + 0x800U) >> 12U) & 0xFFFFFU;
const std::int64_t Low12 = signExtend(Bits, 12);
return static_cast<std::size_t>(High20 != 0) +
static_cast<std::size_t>(Low12 != 0 || High20 == 0);
}
const std::int64_t Low12 = signExtend(Bits, 12);
const std::uint64_t WithoutLow12 = Bits - static_cast<std::uint64_t>(Low12);
std::int64_t Remaining = std::bit_cast<std::int64_t>(WithoutLow12);
std::uint32_t Shift = 0;
if (!fitsSigned(Remaining, 32)) {
Shift = static_cast<std::uint32_t>(std::countr_zero(WithoutLow12));
Remaining >>= Shift;
if (Shift > 12 && !fitsSigned(Remaining, 12)) {
const std::int64_t WithLUILowBits =
std::bit_cast<std::int64_t>(static_cast<std::uint64_t>(Remaining) << 12U);
if (fitsSigned(WithLUILowBits, 32)) {
Shift -= 12;
Remaining = WithLUILowBits;
}
}
}
return baseBuildCost(Remaining) + static_cast<std::size_t>(Shift != 0) +
static_cast<std::size_t>(Low12 != 0);
}
[[nodiscard]] std::optional<std::size_t> leadingZeroBuildCost(std::uint64_t Value) noexcept {
if (Value == 0 || (Value & (std::uint64_t{1} << 63U)) != 0)
return std::nullopt;
const std::uint32_t LeadingZeros = static_cast<std::uint32_t>(std::countl_zero(Value));
const std::uint64_t Shifted = Value << LeadingZeros;
const std::uint64_t LowMask = (std::uint64_t{1} << LeadingZeros) - 1U;
std::optional<std::size_t> Best;
for (const std::uint64_t Candidate : {Shifted | LowMask, Shifted}) {
const std::size_t Cost = baseBuildCost(std::bit_cast<std::int64_t>(Candidate));
if (Cost >= 8)
continue;
const std::size_t WithShift = Cost + 1U;
Best = Best ? std::min(*Best, WithShift) : WithShift;
}
return Best;
}
[[nodiscard]] std::optional<std::size_t> twoRegisterBuildCost(std::int64_t Value) noexcept {
const std::uint64_t Bits = static_cast<std::uint64_t>(Value);
const std::int64_t Low = signExtend(Bits, 32);
if (Low == 0)
return std::nullopt;
const std::uint64_t HighContribution = Bits - static_cast<std::uint64_t>(Low);
if (HighContribution == 0)
return std::nullopt;
const std::uint32_t LowZeros =
static_cast<std::uint32_t>(std::countr_zero(static_cast<std::uint64_t>(Low)));
const std::uint32_t HighZeros = static_cast<std::uint32_t>(std::countr_zero(HighContribution));
if (LowZeros >= 32 || HighZeros < 32 || HighZeros < LowZeros)
return std::nullopt;
const std::uint32_t Shift = HighZeros - LowZeros;
if (Shift >= 64 || HighContribution != (static_cast<std::uint64_t>(Low) << Shift))
return std::nullopt;
return estimateRV64IntegerBuildCost(Low) + 2U;
}
} // namespace
std::size_t estimateRV64IntegerBuildCost(std::int64_t Value) noexcept {
const std::uint64_t Bits = static_cast<std::uint64_t>(Value);
std::size_t Best = baseBuildCost(Value);
if ((Bits & 0xFFFU) != 0 && (Bits & 1U) == 0 && Best >= 2) {
const std::uint32_t TrailingZeros = static_cast<std::uint32_t>(std::countr_zero(Bits));
const std::int64_t Shifted = Value >> TrailingZeros;
const std::size_t Candidate = baseBuildCost(Shifted) + 1U;
if (Candidate < Best || fitsSigned(Shifted, 6))
Best = Candidate;
}
if (Best <= 2)
return Best;
if ((Bits & 0xFFFU) != 0 && (Bits & 0x1800U) == 0x1000U) {
const std::int64_t LastAdd = -static_cast<std::int64_t>(0x800U - (Bits & 0xFFFU));
const std::uint64_t AdjustedBits = Bits - static_cast<std::uint64_t>(LastAdd);
Best = std::min(Best, baseBuildCost(std::bit_cast<std::int64_t>(AdjustedBits)) + 1U);
}
if (Value > 0 && Best > 2) {
if (const auto Candidate = leadingZeroBuildCost(Bits); Candidate && *Candidate < Best)
Best = *Candidate;
} else if (Value < 0 && Best > 3) {
if (const auto Candidate = leadingZeroBuildCost(~Bits); Candidate && *Candidate + 1U < Best) {
Best = *Candidate + 1U;
}
}
return Best;
}
bool shouldUseRV64IntegerConstantPool(std::int64_t Value, std::size_t MaximumBuildCost) noexcept {
if (fitsSigned(Value, 32) || estimateRV64IntegerBuildCost(Value) <= MaximumBuildCost)
return false;
const auto TwoRegisterCost = twoRegisterBuildCost(Value);
return !TwoRegisterCost || *TwoRegisterCost > MaximumBuildCost;
}
} // namespace rcc::riscv
|
