in vm/jitrino/src/optimizer/multiplybyconstant.cpp [660:880]
void planMulCompound(MulMethod &m, inttype d, int depth) {
assert((d < 0) || (d > 31));
DEBUGPRINT("planMulCompound(" << (int) d << ")");
inttype delta = d ^ (d >> 1); // bits differing from from bit to left
int numChanges = popcount<inttype, width>(delta);
int deltaright = ntz<inttype, width>(delta);
int deltaleft = nlz<inttype, width>(delta);
int bitswidth = width - deltaright - deltaleft - 1;
int small_shift_maxbits = m.SMALL_SHIFT_MAXBITS;
if ((numChanges < 4) ||
(bitswidth <= 5)) { // small enough to worry about sign/rightbit issues
DEBUGPRINT("case few changes");
// we assume we've dealt with <31 elsewhere, so we must have some shifting ahead of us.
if ((d & 1) == 1) {
inttype dinv = ~d;
DEBUGPRINT("case odd");
int rightones = ntz<inttype, width>(dinv);
if (rightones == 1) {
inttype dsub1 = d-1;
int dsub1rightzeros = ntz<inttype, width>(dsub1);
if (dsub1rightzeros > small_shift_maxbits) {
planMul<inttype, width>(m,
dsub1 >> small_shift_maxbits,
depth+1);
m.append(MulOp::pushy);
m.append(MulOp::shladd, small_shift_maxbits);
} else {
planMul<inttype, width>(m,
dsub1 >> dsub1rightzeros,
depth+1);
m.append(MulOp::pushy);
m.append(MulOp::shladd, dsub1rightzeros);
}
} else if (rightones <= small_shift_maxbits) {
planMul<inttype, width>(m, (d+1)>>rightones, depth+1);
m.append(MulOp::pushy);
m.append(MulOp::neg);
m.append(MulOp::shladd, rightones);
} else {
planMul<inttype, width>(m, (d+1)>>small_shift_maxbits,
depth+1);
m.append(MulOp::pushy); m.append(MulOp::neg);
m.append(MulOp::shladd, small_shift_maxbits);
}
} else {
DEBUGPRINT("case even");
int rightzeros = deltaright+1;
assert((rightzeros == ntz<inttype, width>(d)));
if (bitswidth <= 5) {
DEBUGPRINT("case narrow");
if ((rightzeros <= small_shift_maxbits) &&
(rightzeros + bitswidth >= 2 * small_shift_maxbits)) {
DEBUGPRINT("case smallshiftadd");
inttype newd = d + ((inttype)1 << rightzeros);
m.append(MulOp::pushy); m.append(MulOp::neg);
planMul<inttype, width>(m, newd, depth+1);
m.append(MulOp::shladd, rightzeros);
} else {
inttype newd = d >> rightzeros;
DEBUGPRINT("case smallshift");
planMul<inttype, width>(m, newd, depth+1);
m.append(MulOp::shiftl, rightzeros);
}
} else {
DEBUGPRINT("case even, wider");
inttype deltasubright = delta - ((inttype)1 << deltaright);
int deltasubright_ntz = ntz<inttype, width>(deltasubright);
int region2 = deltasubright_ntz - deltaright +1;
assert(region2 > 0);
if (region2 > 2) {
inttype newd = d + ((inttype)1 << rightzeros);
if (rightzeros <= small_shift_maxbits) {
DEBUGPRINT("case wide smalladdshift");
m.append(MulOp::pushy); m.append(MulOp::neg);
planMul<inttype, width>(m, newd, depth+1);
m.append(MulOp::shladd, rightzeros);
} else {
DEBUGPRINT("case wide sub of shift");
planMul<inttype, width>(m, newd, depth+1);
m.append(MulOp::pushy); m.append(MulOp::shiftl, rightzeros);
m.append(MulOp::sub);
}
} else if (region2 == 2) {
inttype newd = d - (3 << rightzeros);
DEBUGPRINT("case wide addshift3");
if (rightzeros <= small_shift_maxbits) {
m.append(MulOp::pushy); m.append(MulOp::pushy);
m.append(MulOp::shladd, 1);
planMul<inttype, width>(m, newd, depth+1);
m.append(MulOp::shladd, rightzeros);
} else {
DEBUGPRINT("case wide add shift3");
planMul<inttype, width>(m, newd >> small_shift_maxbits,
depth+1);
m.append(MulOp::pushy); m.append(MulOp::pushy);
m.append(MulOp::shladd, 1);
m.append(MulOp::shiftl, rightzeros);
m.append(MulOp::shladd, small_shift_maxbits);
}
} else { // region2 == 1
inttype newd = d - ((inttype)1 << rightzeros);
if (rightzeros <= small_shift_maxbits) {
DEBUGPRINT("case wide smalladdshift1");
m.append(MulOp::pushy);
planMul<inttype, width>(m, newd, depth+1);
m.append(MulOp::shladd, rightzeros);
} else {
DEBUGPRINT("case wide sub of shift");
planMul<inttype, width>(m, newd >> small_shift_maxbits,
depth+1);
m.append(MulOp::pushy);
m.append(MulOp::shiftl, rightzeros);
m.append(MulOp::shladd, small_shift_maxbits);
}
}
}
}
} else { // bitswidth > 5
assert(numChanges >= 2);
DEBUGPRINT("case wide");
if (numChanges == 2) {
DEBUGPRINT("case numChanges==2");
if ((numChanges&1)==0) {
DEBUGPRINT("case wide changes=2 even");
int rightzeros = deltaright+1;
int leftzeros = deltaleft;
assert((rightzeros == ntz<inttype, width>(d)));
assert((leftzeros == nlz<inttype, width>(d)));
if (rightzeros <= small_shift_maxbits) {
DEBUGPRINT("case wide smallshiftadd");
assert(rightzeros+bitswidth >= 2 * small_shift_maxbits);
m.append(MulOp::pushy); m.append(MulOp::neg);
m.append(MulOp::pushy); m.append(MulOp::shiftl, width - leftzeros);
m.append(MulOp::shladd, rightzeros);
} else {
DEBUGPRINT("case wide narrow sub");
m.append(MulOp::pushy); m.append(MulOp::shiftl, width - leftzeros);
m.append(MulOp::pushy); m.append(MulOp::shiftl, rightzeros);
m.append(MulOp::sub);
}
} else {
DEBUGPRINT("case wide changes=2 odd");
}
} else {
// first try: use point width/2 to split number
DEBUGPRINT("case numChanges>2");
int rightzeros = ((d & 1)!=0) ? 0 : deltaright+1;
#ifndef NDEBUG
int leftzeros = ((d & ((inttype)1<<(width-1))) != 0) ? 0 : deltaleft;
#endif
assert((rightzeros == ntz<inttype, width>(d)));
assert((leftzeros == nlz<inttype, width>(d)));
int k = (numChanges + 1) >> 2;
assert(k > 0); // we had numChanges>=3 above.
inttype stripright = d;
while (k > 0) {
// turn rightmost group of 0s into 1s, no effect if none
inttype striprightzeros = stripright | (stripright - 1);
// turn rightmost group of 1s into 0s, must be some
inttype srzinv = ~striprightzeros; // first invert
inttype sroinv = srzinv | (srzinv - 1); // strip 0s
stripright = ~sroinv; // invert back
k -= 1;
}
// now stripright is d but with 0s from about the middle
// of changes to the right
// find a point one place to the left of the set of 0s
int zeropoint = ntz<inttype, width>(stripright);
inttype zerobit = (inttype(1))<<zeropoint;
assert((d & zerobit) != 0);
assert((d & (zerobit>>1)) == 0);
DEBUGPRINT("zerobit is " << (int) zerobit);
DEBUGPRINT("zeropoint is " << (int) zeropoint);
inttype rightmask = zerobit - 1;
inttype leftmask = ~rightmask;
DEBUGPRINT("leftmask is " << (int) leftmask << ", rightmask is " << (int) rightmask);
inttype rightd = d & rightmask;
inttype leftd = d & leftmask;
DEBUGPRINT("leftd is " << (int) leftd << ", rightd is " << (int) rightd);
int leftdrightzeros = ntz<inttype, width>(leftd);
if (rightzeros == 0) {
DEBUGPRINT("case 0");
if (leftdrightzeros < small_shift_maxbits) {
DEBUGPRINT("case 0a");
planMul<inttype, width>(m, leftd >> leftdrightzeros,
depth+1);
planMul<inttype, width>(m, rightd, depth+1);
m.append(MulOp::shladd, leftdrightzeros);
} else {
planMul<inttype, width>(m, leftd, depth+1);
planMul<inttype, width>(m, rightd, depth+1);
m.append(MulOp::add);
}
} else if ((0 < rightzeros) && (rightzeros <= small_shift_maxbits)) {
DEBUGPRINT("case 1");
planMul<inttype, width>(m, rightd >> rightzeros, depth+1);
planMul<inttype, width>(m, leftd, depth+1);
m.append(MulOp::shladd, rightzeros);
} else {
DEBUGPRINT("case 3");
planMul<inttype, width>(m, leftd >> small_shift_maxbits,
depth+1);
planMul<inttype, width>(m, rightd, depth+1);
m.append(MulOp::shladd, small_shift_maxbits);
}
DEBUGPRINT("done");
}
}
}