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  7810 reads

Browse archives
Active forum topics

Recent comments
7 weeks 2 days ago
11 weeks 4 days ago
13 weeks 1 day ago
13 weeks 1 day ago
15 weeks 6 days ago
20 weeks 3 days ago
20 weeks 3 days ago
20 weeks 6 days ago
20 weeks 6 days ago
23 weeks 5 days ago