Known Bits and Barrel Shifters
This is a quick update post to A Knownbits Abstract Domain for the Toy
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
This is a quick update post to A Knownbits Abstract Domain for the Toy Optimizer, Correctly. I wanted to add knownbits reasoning to shift operations. Checking LLVM, I found out that they implement this with a loop over the possible values of the shift amount. This is a very pragmatic approach and definitely fine in practice. I was still unhappy with it on purity grounds and wanted a principled way to get the same precision with less work, at least in the limit. Then I realized that it should be possible to use a logarithmic barrel shifter to implement shifting of known bits.
In this post I describe both the pragmatic approach and the one based on the barrel shifter.
To recap from the previous post, we are working with a "known bits" abstract domain, that reasons about which bits of the integer variables of a program must have certain fixed values (0 or 1) and which bits are unknown.
For example, if we are shifting the abstract values 0000?101 << ?0, what would the abstract result be? ?0 can be 0 or 10, so the result is either 0000?101 << 0 == 0000?101 or 0000?101 << 10 == 00?10100. Combining these two results gives 0000?101 << ?0 == 00???10?. This combination is taking the approximate union of two abstract values (if we are interpreting the abstract values as sets of concrete values).
In this case we computed this result by enumerating all possible constant values of the shift amount. This approach works generally and is not actually as inefficient as it looks.
Before we start talking about abstract knownbits shift, let's go through a thought exercise. Let's say we wanted to implement a shift function that shifts fixed-width (unsigned) integers in a language that supports only constant shifts. A brute force way to do that would be to check for all the possible shift amounts that the data type supports. For example, to shift 32 bit integers we could write this:
def lshift_enumerated_32(value, amount): assert amount >= 0 if amount == 0: result = value << 0 elif amount == 1: result = value << 1 elif amount == 2: result = value << 2 elif amount == 3: result = value << 3 elif amount == 4: result = value << 4 elif amount == 5: result = value << 5 elif amount == 6: result = value << 6 elif amount == 7: result = value << 7 elif amount == 8: result = value << 8 elif amount == 9: result = value << 9 elif amount == 10: result = value << 10 elif amount == 11: result = value << 11 elif amount == 12: result = value << 12 elif amount == 13: result = value << 13 elif amount == 14: result = value << 14 elif amount == 15: result = value << 15 elif amount == 16: result = value << 16 elif amount == 17: result = value << 17 elif amount == 18: result = value << 18 elif amount == 19: result = value << 19 elif amount == 20: result = value << 20 elif amount == 21: result = value << 21 elif amount == 22: result = value << 22 elif amount == 23: result = value << 23 elif amount == 24: result = value << 24 elif amount == 25: result = value << 25 elif amount == 26: result = value << 26 elif amount == 27: result = value << 27 elif amount == 28: result = value << 28 elif amount == 29: result = value << 29 elif amount == 30: result = value << 30 elif amount == 31: result = value << 31 else: assert amount >= 32 result = 0 return result & 0xffffffff
This is a brute force approach, but gets the job done.
If we wanted to be smarter about this, we can use the fact that shifting is compositional. If we want to shift by 5, we can look at the binary representation of 5 == 4 + 1 == 0b101. Therefore a << 5 == a << (4 + 1) == (a << 4) << 1. This is because shifting composes: a << (b + c) == (a << b) << c. To understand this: a left shift is a multiplication by a power of two, so the product rule of exponents applies: a << (b + c) == a * 2 ** (b + c) == a * 2 ** b * 2 ** c == (a << b) << c. So to compute a shift, we can deconstruct the shift amount into powers of two.
This latter design is the approach how hardware implements shifting. It's called a logarithmic barrel shifter. The barrel shifter consists of log2(integer_width) stages. At every stage we look at a bit of the shift amount. If that bit is set, we shift by the value of that bit in base 2 and pass that value to the next stage. If that bit isn't set, we pass the input value of the stage to the input of the next stage. Here's a diagram for width 8, shifting 237 by 5. You can also edit the input values to experiment:
Type 1-8 bits using 0, 1 or ?. Short inputs have leading zeros. Background colors denote where the bits come from.
Stage 0Input11101101Shift amount00000101<<4copy1101000011101101Control = 1Select shifted branch11010000OutputStage 1Input11010000Shift amount00000101<<2copy0100000011010000Control = 0Select copy branch11010000OutputStage 2Input11010000Shift amount00000101<<1copy1010000011010000Control = 1Select shifted branch10100000OutputRange check00000101Amount is below 8: keep the stage output.10100000Final output
11101101 << 00000101 = 10100000For an unknown control bit, combine both branches: keep a bit only when both agree, otherwise write ?. The final range check includes zero when the shift may be 8 or greater.
; function render() { const fields = [$('value'), $('amount')]; const valid = fields.every(field => /^[01?]{1,8}$/.test(field.value)); for (const field of fields) field.setAttribute('aria-invalid', String(!/^[01?]{1,8}$/.test(field.value))); $('error').textContent = valid ? '' : 'Enter 1-8 bits (0, 1 or ?). The diagram shows the last valid input.'; if (!valid) return; const [value, amount] = fields.map(field => field.value.padStart(8, '0')); const result = calculate(value, amount); let svg = 'Eight-bit known-bits barrel shifterThree stages select a shift or a copy. Unknown controls union both branches. A final range check handles oversized shifts.'; result.stages.forEach((stage, i) => { const y = i * 270; svg += ``; svg += text(10, 32, Stage ${i}, 'font-weight-bold') + text(150, 24, 'Input') + word(150, 35, stage.input, [], false, stage.inputOrigins); svg += text(655, 24, 'Shift amount') + word(655, 35, amount, [stage.index]); // Each surviving source bit is wired to its new position. for (let j = stage.distance; j + word(150, 135, stage.shifted, [], stage.control !== '0', stage.shiftedOrigins) + '';
svg += `` + word(440, 135, stage.input, [], stage.control !== '1', stage.inputOrigins) + '';
svg += text(655, 111, Control = ${stage.control}, 'font-weight-bold');
svg += text(655, 136, stage.control === '?' ? 'Union both branches' : stage.control === '1' ? 'Select shifted branch' : 'Select copy branch', 'small');
if (stage.control !== '0') svg += wire('M254 177 L254 211', true);
if (stage.control !== '1') svg += wire('M544 177 L360 228', true);
svg += word(150, 213, stage.output, [], true, stage.outputOrigins) + text(380, 239, stage.control === '?' ? 'Union → output' : 'Output', 'small');
if (i ';
});
svg += '' + text(10, 857, 'Range check', 'font-weight-bold');
svg += word(655, 838, amount, [0, 1, 2, 3, 4]);
const explanation = result.range === 'inside' ? 'Amount is below 8: keep the stage output.' : result.range === 'outside' ? 'Amount is at least 8: all bits shift out.' : 'Amount may be at least 8: union stage output with 00000000.';
svg += text(150, 906, explanation, 'small');
svg += word(150, 931, result.output, [], true, result.outputOrigins) + text(380, 958, 'Final output', 'font-weight-bold');
$('diagram').innerHTML = svg;
$('result').textContent = `${value} {
[$('value').value, $('amount').value] = button.dataset.example.split(',');
render();
});
render();
$('interactive-controls').hidden = false;
})(globalThis);Concrete barrel shifter
We can use this design to implement a shift function taking fewer lines:
def bit(value, index): """ extract bit from value at position index """ return (value >> index) & 1
def mux(condition, value_if_true, value_if_false): """ ternary operator (using hardware terminology 'mux') """ if condition: return value_if_true else: return value_if_false
def lshift_barrel_32(value, amount): assert amount >= 0 if amount >= 32: result = 0 else: result = value result = mux(bit(amount, 4), result << 16, result) result = mux(bit(amount, 3), result << 8, result) result = mux(bit(amount, 2), result << 4, result) result = mux(bit(amount, 1), result << 2, result) result = mux(bit(amount, 0), result << 1, result) return result & 0xffffffff
The function is for bitwidth 32, so it needs two more stages (for shifts by 16 and by 8) compared to the diagram.
Here's a hypothesis-based unit test that checks that both give the same results:
from hypothesis import strategies, given, settings
@given( strategies.integers(0, 0xffffffff), strategies.integers(0, 100), ) def test_concrete_lshift(value, amount): expected = (value << amount) & 0xffffffff assert lshift_enumerated_32(value, amount) == expected assert lshift_barrel_32(value, amount) == expected
With these concrete implementations in hand, we can go back to implementing abstract knownbits shifting, at least if we manage to shift by constant amounts for them.
We'll start with reusing the relevant parts of the knownbits domain from the previous posts, in the fold for completeness' sake.
from dataclasses import dataclass
@dataclass class KnownBits: ones : int unknowns : int
def post_init(self): if isinstance(self.ones, int): assert self.is_well_formed()
def is_well_formed(self):
a bit cannot be both 1 and unknown
return self.ones & self.unknowns == 0
@staticmethod def from_constant(const : int): """ Construct a KnownBits corresponding to a constant, where all bits are known.""" return KnownBits(const, 0)
@property def knowns(self): """ return an integer where the known bits are set. """
the knowns are just the unknowns, inverted
return ~self.unknowns
@property def zeros(self): """ return an integer where the places that are known zeros have a bit set. """
it's a 0 if it is known, but not 1
return self.knowns & ~self.ones
def is_constant(self): """ Check if the KnownBits instance represents a constant. """
it's a constant if there are no unknowns
return self.unknowns == 0
def contains(self, value : int) -> bool:
""" Check whether the KnownBits instance contains the concrete integer
value. """
check whether value matches the bit pattern. in the places where we
know the bits, the value must agree with ones.
return value & self.knowns == self.ones
def repr(self): if self.is_constant(): return f"KnownBits.from_constant({self.ones})" return f"KnownBits({self.ones}, {self.unknowns})"
def str(self): res = [] ones, unknowns = self.ones, self.unknowns
construct the string representation right to left
while 1: if not ones and not unknowns: break # we leave off the leading known 0s if ones == -1 and not unknowns:
-1 has all bits set in two's complement, so the leading
bits are all 1
res.append('1') res.append("...") break if unknowns == -1:
-1 has all bits set in two's complement, so the leading bits
are all ?
assert not ones res.append("?") res.append("...") break if unknowns & 1: res.append('?') elif ones & 1: res.append('1') else: res.append('0') ones >>= 1 unknowns >>= 1 if not res: res.append('0') res.reverse() return "".join(res)
@staticmethod def from_str(s): """ Construct a KnownBits instance that from a string. String can start with ...1 to mean that all higher bits are 1, or ...? to mean that all higher bits are unknown. Otherwise it is assumed that the higher bits are all 0. """ ones, unknowns = 0, 0 startindex = 0 if s.startswith("...?"): unknowns = -1 startindex = 4 elif s.startswith("...1"): ones = -1 startindex = 4 for index in range(startindex, len(s)): ones <<= 1 unknowns <<= 1 c = s[index] if c == '1': ones |= 1 elif c == '?': unknowns |= 1 return KnownBits(ones, unknowns)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。