Strength reduction of constant multipliers

Due to the number of requests, here comes the C source code I mentioned
in an earlier post. I have cleaned it up some; most notably the code
for dealing with the intermediate representation has been abstracted alot.


As usual, no guarentees and your milage may vary.


Cliff


--------------------------CUT HERE-----------------------------------
/*****************************************************************************/
/* */
/* I N T E G E R M U L T I P L Y */
/* */
/*****************************************************************************/


/* Cost in cycles for integer add */
#define COST_add 1


/* Cost in cycles for integer multiply */
#define COST_mul 16


/* Cost in cycles for integer negation */
#define COST_neg 1


/* Barrel shifters pay a fixed cost for any shift. */
/* The old 68000 would pay 4 for the initial, plus 2 per each bit shifted */
/* Cost in cycles for an initial shift */
#define COST_shl1 1


/* Cost in cycles for a shift by 1 bit */
#define COST_shln 0




/*------------------------------prototypes-----------------------------------*/


/* Create a new intermediate-representation node creating the given constant */
extern Inst *constOp(int32 con);


/* Create a new intermediate-representation node doing "opnum" on the input */
extern Inst *unaryOp(Opnum opnum, Inst *ip);


/* Create a new intermediate-representation node doing "opnum" on the inputs */
extern Inst *binaryOp(Opnum opnum, Inst *ip0, Inst *ip1);


/*------------------------------mul_con_Op-----------------------------------*/
/* Convert an integer multiply by a constant to a series of shifts and adds. */
/* This code assumes that the target can do integer shifts & adds, and that */
/* he has a fixed-cost model for the shift and add/sub instructions. Extra */
/* registers are "free", in the sense that the register allocator yet-to-run */
/* will make spare registers available; i.e. spill costs due to increased */
/* register pressure because of this optimization are not taken into account.*/
/* I assume an optimizer will follow this code and clean up useless moves */
/* and adds-of-zero. */
void mul_con_Op(int32 con, Inst *ip1)
{
    Inst *ip0, *ip2; /* Input node guts */
    uint8 x[33]; /* Need 1 per 32-bits + extra high one */
    int16 i, k, l, m; /* Trash counter */
    uint32 j; /* Used as a mask */
    int16 C; /* Costs calculation */


/* Find cheapest set of shifts/adds that performs the same multiplication, */
/* and compare costs against the cost of a multiply. My heuristic is: If */
/* 2nd highest bit is clear, subtract by power-of-2 for high bit (power-of-2 */
/* computed by successive shifts/adds) and recurse. If 2nd highest bit is */
/* set, subtract next higher power-of-2 from number and recurse. Gather all */
/* the powers-of-2 desired, and determine if you want to shift or add to get */
/* each one of them (then add or sub to get product). */


    for( i=0; i<33; i++) /* Zero costs */
        x[i] = 0;
    i = 31;
    j = 1L<<31; /* Start at top bits */
    while( con ) { /* Still got bits to-do */
        if( con & j ) { /* Found a bit? */
            if( con & (j>>1) ) { /* 2 bits in a row? (11xxx pattern) */
x[i+1] = 1; /* Subtract reversed */
con = (j<<1)-con; /* Compute new, smaller constant */
            } else { /* Else just 1 bit in a row (10xxx pattern) */
x[i] = 2; /* Flag as add power-of-2 */
con -= j; /* Compute new, smaller constant */
            } /* End of either 1 or 2+ bits in a row... */
        } /* End of found bits... */
        j >>= 1; /* Figure next smaller power-of-2 */
        i--; /* Figure log of power-of-2 */
    } /* Repeat till got constant */
    C = 0; /* Cost */
    m = 0;
    for( i=0; i<32; i++) { /* Compute cost */
        if( x[i] ) { /* Need this power of 2? */
            m = i-m; /* Get delta since last power of 2 */
            k = m*COST_add; /* Cost for repeated adds */
            l = COST_shl1+(m-1)*COST_shln; /* Cost for shifting */
            C += ((k < l) ? k : l) +COST_add; /* Take min, plus cost to add res */
            m = i; /* Save for next delta computation */
        } /* Else don't need this power of 2 */
    }
    if( x[32] ) C += COST_neg; /* Need a final negation */


/* With costs in hand, determine to shift/add or multiply. */
    if( C < COST_mul ) { /* Cheaper to shift/add */
        ip0 = constOp(0); /* Start with 0 */
        ip2 = unaryOp(MOV_,ip1); /* Work in a temp */
        m = 0; /* Last power of 2 handy */
        for( i=0; i<32; i++ ) { /* For all shifts/adds */
            if( x[i] ) { /* Need this power of 2? */
m = i-m; /* Powers of 2 to gain */
if( m*COST_add < COST_shl1+(m-1)*COST_shln ) { /* Repeated add */
while( m++ < i ) /* Accumulate powers of 2 */
ip2 = binaryOp(ADD_,ip2,ip2);
} else { /* Else shift left */
ip2 = binaryOp(LSL_,ip2,constOp(m));
} /* End of shift or add... */
ip0 = binaryOp((x[i] == 2) ? ADD_ : SUB_,ip2,ip0);
            } /* End of if need this power of 2... */
        } /* End of for all shifts/adds... */
        if( x[32] ) /* Need final negation? */
            ip0 = unaryOp(NEGATE_,ip0);
    } else /* Else multiply */
        ip0 = binaryOp(MUL_,constOp(con),ip1);


    return ip0;
}
--

Return to the comp.compilers page.
Search the comp.compilers archives again.