[PowerPC] Improve instruction selection bit-permuting operations (32-bit)

The PowerPC backend, somewhat embarrassingly, did not generate an

optimal-length sequence of instructions for a 32-bit bswap. While adding a

pattern for the bswap intrinsic to fix this would not have been terribly

difficult, doing so would not have addressed the real problem: we had been

generating poor code for many bit-permuting operations (by which I mean things

like byte-swap that permute the bits of one or more inputs around in various

ways). Here are some initial steps toward solving this deficiency.

Bit-permuting operations are represented, at the SDAG level, using ISD::ROTL,

SHL, SRL, AND and OR (mostly with constant second operands). Looking back

through these operations, we can build up a description of the bits in the

resulting value in terms of bits of one or more input values (and constant

zeros). For each bit, we compute the rotation amount from the original value,

and then group consecutive (value, rotation factor) bits into groups. Groups

sharing these attributes are then collected and sorted, and we can then

instruction select the entire permutation using a combination of masked

rotations (rlwinm), imm ands (andi/andis), and masked rotation inserts

(rlwimi).

The result is that instead of lowering an i32 bswap as:

rlwinm 5, 3, 24, 16, 23

rlwinm 4, 3, 24, 0, 7

rlwimi 4, 3, 8, 8, 15

rlwimi 5, 3, 8, 24, 31

rlwimi 4, 5, 0, 16, 31

we now produce:

rlwinm 4, 3, 8, 0, 31

rlwimi 4, 3, 24, 16, 23

rlwimi 4, 3, 24, 0, 7

and for the 'test6' example in the PowerPC/README.txt file:

unsigned test6(unsigned x) {

return ((x & 0x00FF0000) >> 16) | ((x & 0x000000FF) << 16);

}

we used to produce:

lis 4, 255

rlwinm 3, 3, 16, 0, 31

ori 4, 4, 255

and 3, 3, 4

and now we produce:

rlwinm 4, 3, 16, 24, 31

rlwimi 4, 3, 16, 8, 15

and, as a nice bonus, this fixes the FIXME in

test/CodeGen/PowerPC/rlwimi-and.ll.

This commit does not include instruction-selection for i64 operations, those

will come later.