On many processors, including the MIPS used in the Replay, division is slower than multipication -- but division is the same as multipication by an inverse. Of course, finding an inverse is a special case of division, so at first glance this doesn't seem to help. If the division is by a constant, though, the inverse can be found at compile time (or looked up in a table, I suspect). http://the.wall.riscom.net/books/proc/ppc/cwg/cwg_ix.html discusses how to do this, from a compiler's-writer point of view (for the PowerPC?, not the MIPS, but the principle's the same).
But what does a disassembler do?
Given the code:
11ef1c: 3c031a41 lui v1,0x1a41
11ef20: 8fa202cc lw v0,716(sp)
11ef24: 00021102 srl v0,v0,0x4
11ef28: 3463a41b ori v1,v1,0xa41b
11ef2c: 00430019 multu v0,v1
11ef30: 00004810 mfhi t1
11ef34: 00099082 srl s2,t1,0x2
how does a disassembler figure out what's really going on?
For people who aren't familiar with MIPS assembly but want to follow along, that's basically equivalent to:
union {longlong together; struct {u32 hi; u32 lo} apart} hilo;
v1 = 0x1a41a41b;
v0 = arg1;
v0 >>= 4;
hilo.together = v0 * v1;
s2 = hilo.apart.hi >> 2;
So, we take a number, divide it by 16, multiply by a magic number, take the high word, divide that by 4, and call it done. That's clear, except for what multiplying by the magic number and taking the high word does.
After reading the page above and solving for the divisor, we get:
(2^32 + x - 1) / x = 0x1a41a41b
2^32 + x - 1 = x * 0x1a41a41b
2^32 - 1 = x * 0x1a41a41a
x = (2^32 - 1)/0x1a41a41a
x = 9.75 (well, close enough)
so the magic sequence is division by 9.75. The shifts before and after additionally divide by 64. 9.75 * 64 = 624, so the whole sequence is division by 624. Not coincidentally, that's the size of a ReplayChannel structure.
-- ToddLarason - 20 Mar 2002
Revision r1.1 - 20 Mar 2002 - 09:23 GMT - ToddLarason
|
Copyright © 2001 by the contributing authors.
All material on this collaboration tool is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.
|
|