base: Optimize and otherwise fix a couple of functions in intmath.hh.
As described in the Jira issue, this replaces the implementation of
isPowerOf2() and power(). It also revamps floorLog2 so that there only
needs to be one implementation and no assumptions about how big certain
types are.
The way power() used to work was to raise a number n to an exponent e
by multiplying n times itself e times. As a warning in this function
explains, this can be quite slow for large e. A much more efficient
way to raise a number to an exponent is to square n over and over, and
to multiply in the current square if that bit of e is set.
n ^ 15 = (n^1) * (n^2) * (n^4) * (n^8)
n^8 = (n^4)^2
n^4 = (n^2)^2
n^2 = n^2
n^1 = n
So that takes 6 multiplications, n^2, (n^2)^2, (n^4)^2, and then each
multipy to compute the final result, instead of 14.
The difference is more pronounced for larger exponents, although you'd
quickly start to overflow a uint64_t.
Jira Issue: https://gem5.atlassian.net/browse/GEM5-140
Change-Id: I0ae05aeba1b5882d2a616613b1679e6206b4cbfe
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/26164
Reviewed-by: Daniel Carvalho <odanrc@yahoo.com.br>
Maintainer: Gabe Black <gabeblack@google.com>
Tested-by: kokoro <noreply+kokoro@google.com>