User loginNavigation 
Tagged Arithmetic OptimizationHas there been a paper describing optimizations to arithmetic for tagged pointer representations? For instance, stealing 1bit to distinguish pointers and integers, and using 0 as the tag value for integers, we don't need to perform any shifting for integer addition in order to normalize the integer back to its tagged representation:  integer i is represented as a word shifted by 1 bit:  word = tag(int) tag(int) = int << 2 = word * 2  int = untag(word) untag(word) = word >> 2 = word / 2  no shift needed; subtraction the same addition = int0 + int1 = tag( untag(word0) + untag(word0) ) = tag( (word0 / 2) + (word1 / 2) ) = tag( (word0 + word1) / 2) = 2 * (word0 + word1) / 2 = word0 + word1  one right shift needed to normalize multiplication = int0 * int1 = tag( untag(word0) * untag(word1) ) = tag( (word0 / 2) * (word1 / 2) ) = tag( word0 * word1 / 4 ) = 2 * word0 * word1 / 4 = word0 * word1 / 2  one left shift needed to normalize division = int0 / int1 = tag( untag(word0) / untag(word1) ) = tag( (word0 / 2) / (word1 / 2) ) = tag(word0 / word1) = 2 * (word0 / word1) etc. Obviously these can be derived from basic arithmetic, but it's a bit tedious, so I was wondering if there was a reference describing a full set of such identities, or any more sophisticated optimizations. Perhaps a tag calculus of sorts. Of course, care must be taken to handle overflow on the word when adding and multiplying, but I think "branch on overflow" is a fairly common instruction, and would provide for an efficient implementation to tweak the result. By naasking at 20090203 00:02  LtU Forum  previous forum topic  next forum topic  other blogs  4354 reads

Browse archivesActive forum topics 
Recent comments
1 hour 39 min ago
1 hour 51 min ago
2 hours 16 min ago
13 hours 20 min ago
19 hours 52 min ago
21 hours 35 min ago
21 hours 44 min ago
21 hours 55 min ago
21 hours 59 min ago
22 hours 4 min ago